Printer Friendly

Packing Tree Degree Sequences.

Special cases of the edge disjoint realizations of two tree degree sequences are considered in this paper. We show that if there is no node which have degree one in both degree sequences, then they always have edgedisjoint caterpillar realizations. By using a probabilistic method, we prove that two tree degree sequences always have edge-disjoint realizations if each vertex is a leaf in at least one of the trees. We also show that the edge-disjoint realization problem is in P for an arbitrary number of tree sequences with the property that each vertex is a non-leaf in at most one of the trees.

On the other hand, we show that the following problem is already NP -complete: given two graphical degree sequences [D.sub.1] and [D.sub.2] such that [D.sub.2] is a tree degree sequence, decide if there exist edge-disjoint realizations of [D.sub.1] and [D.sub.2] where the realization of [D.sub.2] does not need to be a tree.

Finally, we show that efficient approximations for the number of solutions as well as an almost uniform sampler exist for two tree degree sequences if each vertex is a leaf in at least one of the trees.

Povzetek: V clanku so obravnavani posebni primeri povezavno-disjunktnih realizaciji dveh zaporedji stopenj dreves. Pokazano je, da, ce ni vozlisca stopnje ena v obeh zaporedjih, potem imata zaporedji vedno povezavno- disjunktni gosenicni realizaciji. Pokazanje tudi primer, ko je problem NP-poln.

Keywords: edge-disjoint realizations, packing spanning trees, degree sequences, uniform sampling

1 Introduction

Packing degree sequences is related to discrete tomography. The central problem of tomography is to reconstruct spatial objects from lower dimensional projections. The discrete 2D version is to reconstruct a colored grid from vertical and horizontal projections. In the simplest version, this problem is to reconstruct the coloring of an n x m grid with the requirement that each row and column has a specific number of entries for each color. Such colored matrix can be considered as a factorization of the complete bipartite graph [K.sub.n,m]. Indeed, for each color [c.sub.i], the 0-1 matrix of size n x m obtained by replacing [c.sub.i] by 1 and all other colors by 0 is an adjacency matrix of a simple bipartite graph such that the disjoint union of these simple graphs is [K.sub.n,m]. The prescribed number of entries for each color are the degrees of the simple bipartite graphs. Therefore, an equivalent problem is to give a factorization of the complete bipartite graph into subgraphs with prescribed degree sequences.

It is also possible to consider the non-bipartite version of the edge-disjoint realization problem above. Obviously, the sum of the degrees for each vertex must be n - 1 when the complete graph [K.sub.n] is factorized. Therefore, if there are k degree sequences, the last degree sequence is uniquely determined by the first k - 1 degree sequences. When k = 2, the problem is reduced to the degree sequence problem, and can be solved in polynomial time [3, 4]. Unfortunately the problem becomes NP-complete already for k = 3 [1]. However, special cases are polynomially solvable. Such a special case is when one of the degree sequences is almost regular, that is, any two degrees differ by at most 1 [5].

In this paper we consider the case when k = 3, and two of the degree sequences are tree degree sequences. It was already known that this case is tractable [6]. Here we present a new result considering special, caterpillar realizations. Another alternative proof is given for a special subclass of pairs of tree degree sequences that can be extended to an arbitrary number of sequences. The size of the solution space and sampling from it is also discussed. As a negative result, we show that deciding the existence of edge-disjoint realizations for two degree sequences [D.sub.1] and [D.sub.2] is NP-complete even if [D.sub.2] is a tree degree sequence (but its realization does not have to be a tree).

2 Preliminaries

In this section we give the definitions and lemmas needed to state the theorems. The central subject of study in this paper is the edge-disjoint realization problem.

Definition 1. A degree sequence D = ([d.sub.1],..., [d.sub.n]) is a series of non-negative integers. A degree sequence is graphical if there is a vertex labeled simple graph G = (V, E) with V = {[v.sub.1]..., [v.sub.n]} in which the degree of vertex [v.sub.i] is exactly [d.sub.i] for i = 1,..., n. Such graph G is called a realization of D. The edge-disjoint realization problem is the following: given a c x n degree matrix D = {([d.sub.1,1],..., [d.sub.1,n]), ([d.sub.2,1],..., [d.sub.2,n]), ..., ([d.sub.c,1],..., ([d.sub.c,n])}, in which each row of the matrix is a degree sequence, decide if there is an ensemble of edge-disjoint realizations of the degree sequences. Such a set of edge-disjoint graphs is called a realization of the degree matrix. Given two degree sequences D = ([d.sub.1],..., [d.sub.n]) and F = ([f.sub.1],..., [f.sub.n]), their sum is defined as D + F = ([d.sub.1] + [f.sub.1], ..., [d.sub.n] + [f.sub.n]).

For sake of completeness, we define tree degree sequences, path sequences and caterpillars.

Definition 2. Let D = ([d.sub.1],..., [d.sub.n]) be a degree sequence. Then D is called a tree sequence if [[SIGMA].sup.n.sub.i=1] [d.sub.i] = 2n - 2 and each degree is positive. If all of the degrees are 2 except two of them which are 1, then D is called a path sequence. A tree is called a caterpillar if its non-leaf vertices span a path.

We will use the following complexity classes later on.

Definition 3. A decision problem is in NP if a nondeterministic Turing Machine can solve it in polynomial time. An equivalent definition is that a witness proving the "yes " answer to the question can be verified in polynomial time. A counting problem is in #P if it asks for the number of witnesses of a problem in NP. A counting problem in #P is in FP if there is a polynomial running time algorithm which gives the solution. It is -complete if any problem in #P can be reduced to it by a polynomial-time counting reduction.

Definition 4. A counting problem in #P is in FPRAS (Fully Polynomial Randomized Approximation Scheme) if there exists a randomized algorithm such that for any problem instance x and [epsilon], [delta] > 0, it generates an approximation [??] for the solution f, satisfying

P (f/1 + [epsilon] [less than or equal to] [??] [less than or equal to] (1 + [epsilon]) x f) [greater than or equal to] 1 - [delta],

and the algorithm has a time complexity bounded by a polynomial of [absolute value of x], 1/[epsilon] and--log([delta]).

The total variational distance [d.sub.TV](p, [pi]) between two discrete distributions P and [pi] over the set X is defined as

[d.sub.TV](p,[pi]) := [1/2] [summation over (x[member of]X)] [absolute value of p(x) - [pi](x)]

Definition 5. A counting problem in #P is in FPAUS (Fully Polynomial Almost Uniform Sampler) if there exists a randomized algorithm such that for any instance x and [epsilon] > 0, it generates a random element of the solution space following a distribution P satisfying

[d.sub.TV](p, U) [less than or equal to] [epsilon],

where U is the uniform distribution over the solution space, and the algorithm has a time complexity bounded by a polynomial of [absolute value of x] and--log([epsilon]).

The following technical lemma will be used later for constructing edge-disjoint caterpillar realizations.

Lemma 1. For n [greater than or equal to] 4, there are two edge-disjoint Hamiltonian paths in the complete graph [K.sub.n] whose ends are pair-wise different.

Proof. Let V = {[v.sub.1],..., [v.sub.n]), and let the first Hamiltonian path be [v.sub.1], [v.sub.2], [v.sub.3]...,[ v.sub.n]. We are going to show by induction that there is a second Hamiltonian path H starting at [v.sub.2], ending at and using no edge between consecutive integers. For n = 4, the path H = [v.sub.2], [v.sub.4], [v.sub.1], [v.sub.3] does the job. Suppose that n > 4 and that we have a path H' on vertices [v.sub.1],..., [v.sub.n-1] between [v.sub.2] and [v.sub.3]. Since the path has at least three edges, there is an edge [v.sub.i][v.sub.j] for which i, j < n - 1. Replace this edge by edges [v.sub.i] [v.sub.n] and [v.sub.n][v.sub.j] for getting the desired path H.

3 Packing trees

First we consider the problem of edge-disjoint realization of two tree degree sequences without common leaves.

Theorem 2. Let D = ([d.sub.1],..., [d.sub.n]) and F = ([f.sub.1],..., [f.sub.n]) be two tree degree sequences such that [min.sub.i]; {[d.sub.i] + [f.sub.i]} [greater than or equal to] 3. Then D and F have edge-disjoint caterpillar realizations.

Proof. The proof goes by induction on n. Observe that the smallest possible n is 4 to accommodate at least 4 = 2 x 2 leaves (note that each tree has at least two leaves). For n = 4, the only possible pair of degree sequences is (2, 2, 1, 1) and (1,1,2,2). By Lemma 1, these sequences have edge-disjoint realizations.

If n > 4 and both D and F are path sequences, then there exists edge-disjoint Hamiltonian paths, according to Lemma 1.

So we may suppose that at least one of the degree sequences is not a path sequence. As the sum of the degrees in D + F is 4n - 4, there are at least four indices where [d.sub.j] + [f.sub.j] = 3. It is not difficult to see that we can select indices i and j such that, possibly after interchanging the roles of D and F, we have [d.sub.i] [greater than or equal to] 3, [d.sub.j] = 1 and [f.sub.j] = 2.

Modify D and F by removing [d.sub.j] and [f.sub.j] and decreasing [d.sub.i] by 1. This modified D' and F' are tree degree sequences without common leaves on n - 1 vertices, therefore, by induction, D' and F' have edge-disjoint caterpillar realizations [T'.sub.1] and [T'.sub.2], respectively. Modify [T'.sub.1] and [T'.sub.2] as follows. Add back vertex [v.sub.j] and connect it to vertex [v.sub.i] in [T'.sub.1]. The tree [T.sub.1] thus arising is a realization of D. Take a path P in [T'.sub.2] containing all non-leaf vertices and two leaves. Observe that P has at least 3 edges as otherwise F has n - 2 leaves, so D has only two, contradicting to [d.sub.i] [greater than or equal to] 3. Hence P has an edge [v.sub.k][v.sub.l] such that k [not equal to] i and t [not equal to] i. For constructing [T.sub.2], replace edge [v.sub.k][v.sub.l] of [T'.sub.2] by two edges, [v.sub.k][v.sub.j] and [v.sub.j][v.sub.l]. The tree [T.sub.2] thus obtained is a caterpillar, edge-disjoint from [T.sub.1] and is a realization of F.

The theorem implicitly states that if two tree degree sequences do not share common leaves then their sum is graphical. If the two trees have common leaves, their sum is not necessarily graphical as shown by the example D = (2,1,1) and F = (2,1,1). Observe that the largest degree in D + F is 4, and there are only 3 vertices.

On the other hand, if the sum of the two sequences happens to be graphical, then they also have edge-disjoint realizations, as was shown by Kundu in [6].

Theorem 3 ([6]). Let D = ([d.sub.1],..., [d.sub.n]) and F = ([f.sub.1], ..., [f.sub.n]) be two tree degree sequences. Then there exist edge-disjoint tree realizations of D and F if and only if D + F is graphical.

However, there are tree degree sequences that have edge-disjoint tree realizations but do not have edge-disjoint caterpillar realizations. For example, consider the tree degree sequences

D = (5,2,2,2,2,2,1,1,1,1,1)

and

F=( 5,2,2,2,2,2,1,1,1,1,1).

According to Theorem 3, these sequences have edge-disjoint realizations as their sum is graphical (see Fig. 1). We claim that they do not have edge-disjoint caterpillar realizations. To see this, observe that in any caterpillar realization, the degree 5 vertices must be connected to at least 3 leaves. However, there are only 5 vertices that are leaves in any of the trees, showing that any pair of caterpillar realizations will share at least one edge.

Theorem 2 considered the case when the leaf vertices of the degree sequences do not coincide. Now we turn to the opposite end, namely when each vertex is a leaf in at least one of the sequences.

Theorem 4. Let D = ([d.sub.1],..., [d.sub.n]) and F = ([f.sub.1],..., [f.sub.n]) be tree degree sequences such that mm([d.sub.i], [f.sub.i]) = 1 for all i. Let [T.sub.1] and [T.sub.2] be random realizations of D and F uniformly distributed. Then the expected number of common edges of [T.sub.1] and [T.sub.2] is 1.

Proof. The proof is based on the following lemma.

Lemma 5. Let T be a random realization of the tree degree sequence D = ([d.sub.1],..., [d.sub.n]) (where n [greater than or equal to] 3). Then the probability of having an edge between [v.sub.i] and [v.sub.j] is

[d.sub.i] + [d.sub.j] - 2/n - 2

Proof. It is well known that the number of trees with a given degree sequence is

(n - 2)!/[[PI].sup.n.sub.k=1] ([d.sub.k] - 1)!.

Let T' denote those trees in which [v.sub.i] and [v.sub.j] are adjacent. Let f be a mapping from T' to the set of trees with degree sequence

([d.sub.1],..., [d.sub.i-1], [d.sub.i+1],..., [d.sub.j-1], [d.sub.j+1],..., [d.sub.n], [d.sub.i] + [d.sub.j] - 2)

obtained by joining [v.sub.i] and [v.sub.j] to a common vertex. The function f is surjective, and each tree is an image [mathematical expression not reproducible] times. Therefore the number of trees in which [v.sub.i] is adjacent to [v.sub.j] is

[mathematical expression not reproducible] (2)

The probability that [v.sub.i] is adjacent to [v.sub.j] is the ratio of (2) and (1), which is indeed

[d.sub.i] + [d.sub.j] - 2/n - 2,

thus concluding the proof of the lemma.

Now we turn to the proof of the theorem. Let D and F be degree sequences satisfying that each vertex is a leaf in at least one of the trees. Define

A := {i | [d.sub.i] > 1 [and] [f.sub.i] = 1}, and B := {i | [d.sub.i] = 1 [and] [f.sub.i] > 1}.

Note that there might be parallel edges in the two trees only between these two sets. The expected number of parallel edges is then

[mathematical expression not reproducible]

since [d.sub.i] = 1 for all i [member of] [bar.A], [f.sub.j] = 1 for all j [member of] [bar.B] and the sum of the degrees decreased by 1 is n - 2 for any tree degree sequence. This finishes the proof of the theorem.

Theorem 4 implies a characterization of realizability for a subclass of tree degree sequences.

Corollary 6. Let D = ([d.sub.1],..., [d.sub.n]) and F = ([f.sub.1],..., [f.sub.n]) E > e iree degree sequences such that each vertex is a leaf in at least one of them. Then D and F have edge-disjoint tree realizations if and only if [d.sub.i] < n - 1 and [f.sub.i] < n - 1 for all i.

Proof. If [max.sub.i]{[d.sub.i]} = n - 1 or [max.sub.i] {[f.sub.i]} = n - 1 then D + F is not graphical. On the other hand, if none of the trees is a star, then there are four distinct indices [i.sub.i], [i.sub.2], [j.sub.1] and [j.sub.2] such that [i.sub.1], [i.sub.2] [member of] A and [j.sub.1], [j.sub.2] [member of] B. Then there exists a pair of trees [T.sub.1] and [T.sub.2] such that both trees contain edges [mathematical expression not reproducible] and [T.sub.1] realizes D while [T.sub.2] realizes F. Indeed, the degree 1 vertices can be connected to any of the non-leaf vertices. This means that the two sequences have realizations having at least 2 common edges, which is above the expected value. Hence there must also exist a realization with less common edges than the expected number, which is 1. That is, there exists an edge-disjoint realization of the two sequences, thus concluding the proof.

This theorem will be useful also at generating random realizations, see the next section.

Similar theorem holds for more tree sequences as well. Let us fix again V = {[v.sub.1],..., [v.sub.n]). We need the following technical preliminary lemma.

Lemma 7. Let D = ([d.sub.1],..., [d.sub.n]) be a tree degree sequence, n > m > 2 and U = {[v.sub.i] | [d.sub.i] > 1}. Suppose [V.sub.1],..., [V.sub.m-1] are pairwise disjoint sets in L = V U. Suppose further that [absolute value of U] > 1, [absolute value of [V.sub.1] > 1,..., [absolute value of [V.sub.m-1]] > 1 and [d.sub.i] [less than or equal to] n - m for all i. Then there is a tree T realizing D such that its restriction to U [union] [V.sub.j] is a non-star tree for all j.

Proof. For any tree realization T, its restriction to U [union] [V.sub.j], is a tree because outside U there are only leaves. In the case [absolute value of U] [greater than or equal to] 4 we claim that there is a tree realization T such that its restriction to U is not a star. Indeed, if T restricted to U is a star centered at u [member of] U, then, by the degree bound, there is a leaf w [member of] L not connected to u. Let [u.sub.1] [member of] U denote the unique neighbor of w in the tree, and let [u.sub.2] be a third vertex of U. Replacing edges u[u.sub.2] and [u.sub.1]w by edges [u.sub.1] [u.sub.2] and uw gives another tree realization T whose restriction to U is not a star.

For the case [absolute value of U] = 2, let U = {[v.sub.i], [v.sub.j]}. Connect first [v.sub.i] to [v.sub.j]. Now [d.sub.i] + [d.sub.j] = n, so [d.sub.i] [greater than or equal to] m and [d.sub.j] [greater than or equal to] m. For each k [less than or equal to] m - 1, connect one vertex of [V.sub.k] to [v.sub.i] and another one to [v.sub.j]. The remaining leaves in L can be distributed easily: connect any [d.sub.i] - m of them to [v.sub.i] and the remainder to [v.sub.j], giving the aimed tree realization.

Finally suppose U = {[v.sub.i], [v.sub.j], [v.sub.k]}. We may also suppose that 2 [less than or equal to] [d.sub.i] [less than or equal to] [d.sub.j] [less than or equal to] [d.sub.k]. Connect first [v.sub.i], and [v.sub.j] to [v.sub.k]. It is easy to connect vertices of L to U in such a way that for each l [less than or equal to] to m - 1, at least one vertex of [V.sub.l] is connected to either [v.sub.j] or [v.sub.k].

Theorem 8. Let [D.sub.1], [D.sub.2],..., [D.sub.m] be tree degree sequences with [D.sub.i] = [d.sub.i,1], [d.sub.i,2],..., [d.sub.i,n] such that each vertex is a leaf in all except at most one of them. Then [D.sub.1], [D.sub.2], ..., [D.sub.m] have edge-disjoint realizations if and only if [max.sub.i,j] {[d.sub.i,j]} [greater than or equal to] n - m.

Proof. Necessity is clear as [D.sub.1] + [D.sub.2] + *** + [D.sub.m] is not graphical if [max.sub.i,j] {[d.sub.i,j]} > n - m.

The statement is trivial when to m = 1. If to = 2 then it is equivalent to Corollary 6, so we may suppose m > 2.

We give a constructive proof for the other direction. First a trial solution is built which might contain parallel edges, then these parallel edges are eliminated to get an edge-disjoint realization.

Let [V.sub.i] denote the subset of vertices on which the degrees in [D.sub.i] are larger than 1. Note that {[V.sub.1], [V.sub.2],..., [V.sub.m]} forms a subpartition of V and [absolute value of [V.sub.i]] [greater than or equal to] 2 for each i = 1,... ,m. For a degree sequence [D.sub.i], construct a trial tree [[??].sub.i] by using Lemma 7, which ensures that the subtree on vertices [V.sub.i] [union] [V.sub.k] is a non-star tree for any k [not equal to] i.

From the trial solution, which might contain several parallel edges, a final solution is built in the following way. While there exists a pair of indexes (i, k) such that there is one or more parallel edges between [V.sub.i] and [V.sub.k], do the following. Let [[??].sub.i,k] denote the subtree of the tree [[??].sub.i] on vertices [V.sub.i] [union] [V.sub.k] and let [[??].sub.i,k] denote its degree sequence. By Corollary 6, [[??].sub.i,k] and [[??].sub.k,i] have edge-disjoint tree realizations. Replace [[??].sub.i,k] and [[??].sub.k,i] by such realizations. This removes all parallel edges between [V.sub.i] and [V.sub.k] because [[??].sub.j] has no edge between these sets if j [not equal to] i, j [not equal to] k.

4 Counting and sampling realizations

Since typically there are more than one realizations when a realization exists, and typically the number of realizations might grow exponentially, it is also a computational challenge to estimate their number and/or sample almost uniformly a solution. Here we prove the following theorem.

Theorem 9. Let D = ([d.sub.1],..., [d.sub.n]) and F = ([f.sub.1],..., [f.sub.n]) be two tree degree sequences such that each vertex is a leaf in at least one of the trees. Furthermore, assume that none of the trees is a star. Then there is an FPRAS for estimating the number of disjoint realizations and there is an FPAUS for almost uniformly sampling realizations.

Proof This theorem is based on Theorem 4. As we discussed, there are random trees with at least two parallel edges. The number of pair of trees containing parallel edges [mathematical expression not reproducible] such that [mathematical expression not reproducible] and

[mathematical expression not reproducible] (3)

Therefore, at least the same number of pair of trees have no parallel edges (that is, are edge-disjoint realizations of the degree sequences) to get the expectation 1 for the number of parallel edges. Therefore, the probability that two random trees will be edge-disjoint is at least

[mathematical expression not reproducible].

It follows from basic probabilistic arguments that an FPRAS algorithm can be designed based on this property. Indeed, let [xi] be the indicator variable that a random pair of trees are edge-disjoint realizations. Then the number of edge-disjoint realizations is

E[[xi]] (n - 2)!/[[PI].sup.n.sub.k=1]([d.sub.i] - 1)! (n - 2)!/[[PI].sup.n.sub.k=1]([f.sub.i] - 1).

Furthermore, we know that

[mathematical expression not reproducible].

Uniformly distributed random trees with a prescribed degree sequence can be generated in polynomial time based on the fact that the probability that a given leaf is connected to a vertex with degree [d.sub.i] is

[d.sub.i] - 1/n - 2.

A uniformly distributed tree can be generated by randomly selecting a neighbor of a given leaf, then generating a random tree for the remaining degree sequence. Equivalently, the trees with a prescribed degree sequence can be encoded by the Pruffer codes in which the index i appears exactly [d.sub.i] - 1 times. Uniformly generating such Pruffer codes is an elementary computational task.

Therefore, random pair of trees can be generated in polynomial time, and it is easy to check whether or not they are edge-disjoint realizations. Such sampling of random trees provide an unbiased estimation for the expectation of the indicator variable [xi]. Indeed, if [X.sub.i] is 1 if the ith pair of random trees are edge-disjoint and 0 otherwise, then the random variable

[Y.sub.m] := [summation over (i=1)] [X.sub.i]

follows a binomial distribution with parameter p = E[[xi]] and expectation mE[[xi]]. The tails of the binomial distributions can be bounded by the Chernoff's inequality:

P([Y.sub.m] [less than or equal to] mp (1 - [epsilon])) [less than or equal to] exp (- 1/2p ([m.sub.p] - mp [(1 - [epsilon])).sup.2]/m).

This should be bounded by [delta]/2 (the other half [delta] error will go to the other tail)

exp (- 1/2p (mp - mp[(1 - [epsilon])).sup.2]/m) [less than or equal to] [delta]/2. (4)

Solving Equation 4, we get

m [greater than or equal to] -2 log([delta]/2)/p[[epsilon].sup.2].

For the upper tail, we can also use the Chernoff's inequality, just replacing P with 1 - p and the upper threshold mp(1 + [epsilon]) with m - mp(1 + [epsilon]):

P([Y.sub.m] [greater than or equal to] mp(1 + [epsilon])) [less than or equal to] exp( -(m(1 - p) - (m - mp[(1 + [epsilon]))).sup.2]/2(1 - p) m).

Upper bounding this with [delta]/2 and solving the inequality, we get that

m [greater than or equal to] -2(1 - p) log ([delta]/2)/[p.sup.2][[epsilon].sup.2].

Since 1/p = O([n.sup.4]), the necessary number of samples is indeed polynomial with the size of the problem, 1/e and - log([delta]). Furthermore, one sample can be generated in polynomial time, therefore this algorithm is indeed an FPRAS.

It is also well known that an FPAUS algorithm can be designed in this case. The FPAUS algorithm generate -log([epsilon])/p pair of random trees. If any of them is an edge-disjoint realization, then the algorithm returns with it. Otherwise it generates an arbitrary realization and returns with it.

This is indeed an FPAUS algorithm, since any random pair of trees which are edge-disjoint come from sharp the uniform distribution of the solutions. The probability that there will be no edge-disjoint pair of trees in m number of samples is

[(1 - p).sup.m].

This probability is not larger than [epsilon]. Indeed,

(1 - p) -log([epsilon]/p) [less than or equal to] [epsilon],

since

-log([epsilon])/p log(1 - p) [less than or equal to] log ([epsilon])/p

because

-log(1 - p) [greater than or equal to] p.

Namely, the algorithm generates realizations from a distribution which is the convex combination (1 - [epsilon]')U + [epsilon]'[pi], where [epsilon]' [less than or equal to] [epsilon], U is the uniform distribution and [pi] is an arbitrary distribution. However, the variational distance of this distribution from the uniform one is

[mathematical expression not reproducible]

Since one sample can be generated in polynomial time, and the total number of samples is polynomial with the size of the problem and - log([epsilon]), this algorithm is indeed and FPAUS.

It remains an open question whether or not similar theorems exist for the case when the tree degree sequences have common high degrees. Also it is open if exact counting of the edge-disjoint solutions is possible in polynomial time, although the natural conjecture is that this counting problem is #P-complete.

5 A complexity result

What can we say when only one of the two degree sequences is a tree degree sequence and the other is arbitrary? Unfortunately, we have a negative result here.

Theorem 10. It is NP-complete to decide if a tree degree sequence and an arbitrary degree sequence have an edge-disjoint realization (in which the tree degree sequence does not necessarily have to be represented by a tree).

Proof. By [1], it is NP-complete to decide if two bipartite degree sequences has edge-disjoint realizations. We have the following observations.

Claim 1. A bipartite degree sequence pair

[mathematical expression not reproducible]

and

[mathematical expression not reproducible]

has an edge disjoint realization if and only if the simple degree sequence pair

[mathematical expression not reproducible]

and

[mathematical expression not reproducible]

has an edge-disjoint realization.

Proof. If an edge-disjoint bipartite realization of D and F is given, then the complete graph on the first vertex class can be added to the first realization and the complete graph on the second vertex class can be added to the second realization to get a (now non-bipartite) realization of D' and F'. On the other hand, it is easy to see that any realization of D' contains [mathematical expression not reproducible] on the first [n.sub.1] vertices, and any realization of F' contains [mathematical expression not reproducible] on the last [n.sub.2] vertices. Given an edge-disjoint realization of D' and F', deleting [mathematical expression not reproducible] from D' and [mathematical expression not reproducible] from F' yields an edge-disjoint realization of D and F.

Claim 2. The degree sequence pair D = ([d.sub.1],..., [d.sub.n]) and F = ([f.sub.1],..., [f.sub.n]) has an edge-disjoint realization if and only if the degree sequence pair D' = ([d.sub.1] + 1,..., [d.sub.n] + 1, n) and F' = ([f.sub.1],..., [f.sub.n], 0) has an edge-disjoint realization.

Proof. Let [G.sub.1] and [G.sub.2] be an edge-disjoint realization of D and F. Then add a vertex [v.sub.n+1] to [G.sub.1], and connect it to all the other vertices to get a realization of D'. Add an isolated vertex [v.sub.n+1] to [G.sub.2] to get a realization of F'. These realizations of D' and F' are edge-disjoint. On the other hand, in any realization of D', [v.sub.n+1] is connected to all the other vertices. If edge-disjoint realizations of D' and F' are given, delete [v.sub.n+1] from both realizations to get edge-disjoint realizations of D and F.

Claim 3. The degree sequence pair D = ([d.sub.1],...., [d.sub.n]) and F = ([f.sub.1],..., [f.sub.n]) has an edge-disjoint realization if and only if the degree sequence pair D' = ([d.sub.1],..., [d.sub.n], 1,1) and F' = ([f.sub.1] + 1, ...,[f.sub.n] + 1, n, 0) has an edge-disjoint realization.

Proof Any edge-disjoint realization [G.sub.1] and [G.sub.2] of D and F can be extended to an edge-disjoint realization of D' and F' by adding two vertices [v.sub.n+1] and [v.sub.n+2], and then connecting [v.sub.n+1] to all [v.sub.1],..., [v.sub.n] in [G.sub.2] and connecting [v.sub.n+1] and [v.sub.n+2] in [G.sub.1]. On the other hand, in any edge-disjoint realizations [G'.sub.1] and [G'.sub.2] of D' and F', [v.sub.n+1] is connected to all [v.sub.1],..., [v.sub.n] in [G'.sub.2], therefore, [v.sub.n+1] must be connected to [v.sub.n+2] in [G'.sub.1]. Therefore deleting [v.sub.n+1] and [v.sub.n+2] yields an edge-disjoint realization of D and F.

We can use Claim 1 to prove that it is NP-complete to decide if two simple degree sequences have edge-disjoint realizations. Claim 2 shows that it is NP-complete to decide if two degree sequences have edge-disjoint realizations such that one of the degree sequences does not have 0 degrees. Finally, Claim 3 can be used to iteratively transform any D degree sequence (that already does not have a 0 degree) into a tree degree sequence. Indeed, in each step, we add two vertices to D and extend the sum of the degrees only by 2. Therefore in a polynomial number of steps, we get a degree sequence D' in which the sum of the degrees is exactly twice the number of vertices minus 2. Therefore it follows that given any bipartite degree sequences D and F, we can construct in polynomial time two simple degree sequences D' and F' such that D and F have edge-disjoint realizations if and only if D' and F' have edge-disjoint realizations, furthermore, D' is a tree degree sequence.

6 Discussion and conclusions

In this paper, we considered packing tree degree sequences. When there are no common leaves, there are always edge-disjoint caterpillar realizations. On the other hand, there might not be edge-disjoint caterpillar realizations when there are common leaves, even if otherwise there are edge-disjoint tree realizations.

When there are no common high degree vertices, there are edge-disjoint tree realizations if and only if none of the degree sequences is a degree sequence of a star. Similar theorem exists for arbitrary number of trees, and it is easy to decide if arbitrary number of tree degree sequences without common high degrees have edge-disjoint realizations.

It is also known [5] that a degree sequence and an almost regular degree sequence have an edge-disjoint realization if and only if their sum is graphical. This raises the natural question if a degree sequence and a tree sequence have edge-disjoint realizations if and only if their sum is graphical. We showed that the answer is no to this question, and actually it is NP-complete to decide if an arbitrary degree sequence and a tree degree sequence have edge-disjoint realizations.

We also showed hot to approximately count and sample edge-disjoint tree realizations with prescribed degrees. We proved that this is possible if there are no common high degree vertices. However, when the two degree sequences have common high degree vertices then the problem remains open.

References

[1] Durr, C., Guinez, F., Matamala, M.: Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard. European Symposium on Algorithms, 776-787 (2009)

[2] Erdos, P.; Gallai, T. : Graphs with vertices of prescribed degrees (in Hungarian) Matematikai Lapok, 11: 264-274. (1960)

[3] S.L. Hakimi: On the degrees of the vertices of a directed graph. J. Franklin Institute, 279(4):290-308. (1965)

[4] V. Havel: A remark on the existence of finite graphs. (Czech), Casopis Pest. Mat. 80:477-480. (1955)

[5] Kundu, S.: The k-factor conjecture is true. Discrete Mathematics, 6(4):367-376. (1973)

[6] Kundu, S.: Disjoint Representation of Tree Realizable Sequences. SIAM Journal on Applied Mathematics, 26(1): 103-107. (1974)

Caption: Figure 1: Edge-disjoint realization of two degree sequences, both of them are (5,2,2,2,2,2,1,1,1,1,1)

Kristof Berczi

Department of Operations Research and MTA-ELTE Egervary Research Group

Eotvos Lorand University

Pazmany Peter setany 1/c, 1117 Budapest, Hungary

E-mail: berkri@cs.elte.hu

Zoltan Kiraly

Department of Computer Science and MTA-ELTE Egervary Research Group

Eotvos Lorand University

Pazmany Peter setany 1/c, 1117 Budapest, Hungary

E-mail: kiraly@cs.elte.hu

Changshuo Liu

Budapest Semesters in Mathematics

Bethlen Gabor ter 2, 1071 Budapest, Hungary

E-mail: cl20@princeton.edu

Istvan Miklos

Renyi Institute

Realtanoda u. 13-15, 1053 Budapest. Hungary

E-mail: miklos.istvan@renyi.mta.hu

Received: October 30, 2018

https://doi.org/10.31449/inf.v43i1.2675
COPYRIGHT 2019 Slovenian Society Informatika
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2019 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Berczi, Kristof; Kiraly, Zoltan; Liu, Changshuo; Miklos, Istvan
Publication:Informatica
Article Type:Report
Geographic Code:4EXHU
Date:Mar 1, 2019
Words:6093
Previous Article:Implementation and Evaluation of Algorithms with ALGator.
Next Article:Construction of Orthogonal CC-sets.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters