https://doi.org/10.31449/inf.v43i1.2675 Informatica 43 (2019) 11–17 11 Packing Tree Degree Sequences Kristóf Bérczi Department of Operations Research and MTA-ELTE Egerváry Research Group Eötvös Loránd University Pázmány Péter sétány 1/c, 1117 Budapest, Hungary E-mail: berkri@cs.elte.hu Zoltán Király Department of Computer Science and MTA-ELTE Egerváry Research Group Eötvös Loránd University Pázmány Péter sétány 1/c, 1117 Budapest, Hungary E-mail: kiraly@cs.elte.hu Changshuo Liu Budapest Semesters in Mathematics Bethlen Gábor tér 2, 1071 Budapest, Hungary E-mail: cl20@princeton.edu István Miklós Rényi Institute Reáltanoda u. 13-15, 1053 Budapest, Hungary E-mail: miklos.istvan@renyi.mta.hu Keywords: edge-disjoint realizations, packing spanning trees, degree sequences, uniform sampling Received: October 30, 2018 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 edge- disjoint 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 1 and D 2 such that D 2 is a tree degree sequence, decide if there exist edge-disjoint realizations ofD 1 andD 2 where the realization ofD 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 vozlišˇ ca stopnje ena v obeh zaporedjih, potem imata zaporedji vedno povezavno- disjunktni goseniˇ cni realizaciji. Pokazan je tudi primer, ko je problemNP -poln. 1 Introduction Packing degree sequences is related to discrete tomogra- phy. 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 ann m grid with the requirement that each row and column has a spe- cific number of entries for each color. Such colored matrix can be considered as a factorization of the complete bipar- tite graphK n;m . Indeed, for each colorc i , the 0-1 matrix of sizen m obtained by replacingc 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 isK 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 com- plete bipartite graph into subgraphs with prescribed degree sequences. 12 Informatica 43 (2019) 11–17 K. Bérczi et al. 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 ben 1 when the complete graph K n is factorized. Therefore, if there are k degree sequences, the last degree sequence is uniquely determined by the firstk 1 degree sequences. Whenk = 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 fork = 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 real- izations. Another alternative proof is given for a special subclass of pairs of tree degree sequences that can be ex- tended 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 sequencesD 1 and D 2 is NP-complete even if D 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 1 ;:::;d 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 = fv 1 ;:::;v n g in which the de- gree of vertex v i is exactly d 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 n degree matrix D = f(d 1;1 ;:::;d 1;n ); (d 2;1 ;:::;d 2;n ); :::; (d c;1 ;:::;d c;n )g, 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 1 ;:::;d n ) andF = (f 1 ;:::;f n ), their sum is defined asD +F = (d 1 +f 1 ;:::;d n +f n ). For sake of completeness, we define tree degree se- quences, path sequences and caterpillars. Definition 2. LetD = (d 1 ;:::;d n ) be a degree sequence. ThenD is called atreesequence if P n i=1 d i = 2n 2 and each degree is positive. If all of the degrees are 2 except two of them which are 1, thenD is called apathsequence. 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 non- deterministic 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 num- ber of witnesses of a problem in NP. A counting problem in #P is in FP if there is a polynomial running time al- gorithm which gives the solution. It is #P-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 prob- lem instancex and;> 0, it generates an approximation ^ f for the solutionf, satisfying P f 1 + ^ f (1 + ) f 1 ; and the algorithm has a time complexity bounded by a poly- nomial ofjxj, 1= and log( ). The total variational distance d TV (p; ) between two discrete distributions P and over the setX is defined as d TV (p; ) := 1 2 X x2X jp(x) (x)j 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 > 0, it generates a random element of the solution space following a distribution P satisfying d TV (p;U) ; whereU is the uniform distribution over the solution space, and the algorithm has a time complexity bounded by a poly- nomial ofjxj and log( ). The following technical lemma will be used later for constructing edge-disjoint caterpillar realizations. Lemma 1. Forn 4, there are two edge-disjoint Hamilto- nian paths in the complete graphK n whose ends are pair- wise different. Proof. LetV =fv 1 ;:::;v n g, and let the first Hamiltonian path bev 1 ;v 2 ;v 3 :::;v n . We are going to show by induc- tion that there is a second Hamiltonian pathH starting at v 2 , ending atv 3 and using no edge between consecutive in- tegers. Forn = 4, the pathH =v 2 ;v 4 ;v 1 ;v 3 does the job. Suppose thatn> 4 and that we have a pathH 0 on vertices v 1 ;:::;v n 1 betweenv 2 andv 3 . Since the path has at least three edges, there is an edgev i v j for whichi;j < n 1. Replace this edge by edgesv i v n andv n v j for getting the desired pathH. Packing Tree Degree Sequences Informatica 43 (2019) 11–17 13 3 Packing trees First we consider the problem of edge-disjoint realization of two tree degree sequences without common leaves. Theorem 2. LetD = (d 1 ;:::;d n ) andF = (f 1 ;:::;f n ) be two tree degree sequences such that min i fd i +f i g 3. ThenD andF have edge-disjoint caterpillar realizations. Proof. The proof goes by induction onn. Observe that the smallest possiblen is 4 to accommodate at least 4 = 2 2 leaves (note that each tree has at least two leaves). Forn = 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 se- quences is not a path sequence. As the sum of the degrees inD +F is 4n 4, there are at least four indices where d j +f j = 3. It is not difficult to see that we can select indicesi andj such that, possibly after interchanging the roles ofD andF , we haved i 3,d j = 1 andf j = 2. ModifyD andF by removingd j andf j and decreasing d i by 1. This modifiedD 0 andF 0 are tree degree sequences without common leaves on n 1 vertices, therefore, by induction,D 0 andF 0 have edge-disjoint caterpillar realiza- tionsT 0 1 andT 0 2 , respectively. ModifyT 0 1 andT 0 2 as follows. Add back vertexv j and connect it to vertexv i inT 0 1 . The treeT 1 thus arising is a realization ofD. Take a path P in T 0 2 containing all non-leaf vertices and two leaves. Observe that P has at least 3 edges as otherwiseF hasn 2 leaves, soD has only two, contradicting tod i 3. Hence P has an edgev k v ‘ such thatk6= i and‘6= i. For constructingT 2 , replace edgev k v ‘ ofT 0 2 by two edges,v k v j andv j v ‘ . The treeT 2 thus obtained is a caterpillar, edge-disjoint fromT 1 and is a realization ofF . The theorem implicitly states that if two tree degree se- quences 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) andF = (2; 1; 1). Observe that the largest degree inD +F is 4, and there are only 3 vertices. On the other hand, if the sum of the two sequences hap- pens to be graphical, then they also have edge-disjoint re- alizations, as was shown by Kundu in [6]. Theorem 3 ([6]). Let D = (d 1 ;:::;d n ) and F = (f 1 ; :::;f 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 de- gree sequences D = (5; 2; 2; 2; 2; 2; 1; 1; 1; 1; 1) Figure 1: Edge-disjoint realization of two degree se- quences, both of them are (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 re- alizations. To see this, observe that in any caterpillar real- ization, 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 re- alizations 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. LetD = (d 1 ;:::;d n ) andF = (f 1 ;:::;f n ) be tree degree sequences such that min(d i ;f i ) = 1 for alli. LetT 1 andT 2 be random realizations ofD andF uniformly distributed. Then the expected number of common edges of T 1 andT 2 is 1. Proof. The proof is based on the following lemma. Lemma 5. Let T be a random realization of the tree de- gree sequenceD = (d 1 ;:::;d n ) (wheren 3). Then the probability of having an edge betweenv i andv j is d i +d j 2 n 2 : Proof. It is well known that the number of trees with a given degree sequence is (n 2)! Q n k=1 (d k 1)! : (1) LetT 0 denote those trees in whichv i andv j are adjacent. Letf be a mapping fromT 0 to the set of trees with degree sequence (d 1 ;:::;d i 1 ;d i+1 ;:::;d j 1 ;d j+1 ;:::;d n ;d i +d j 2) 14 Informatica 43 (2019) 11–17 K. Bérczi et al. obtained by joining v i and v j to a common vertex. The function f is surjective, and each tree is an image di+dj 2 di 1 times. Therefore the number of trees in which v i is adjacent tov j is (n 3)! (di+dj 3)! Q k6=i;j (d k 1)! (di+dj 2)! (di 1)!(dj 1)! = (di+dj 2)(n 3)! Q n k=1 (d k 1)! : (2) The probability thatv i is adjacent tov j is the ratio of (2) and (1), which is indeed d i +d j 2 n 2 ; thus concluding the proof of the lemma. Now we turn to the proof of the theorem. LetD andF be degree sequences satisfying that each vertex is a leaf in at least one of the trees. Define A := fijd i > 1^f i = 1g;and B := fijd i = 1^f i > 1g: Note that there might be parallel edges in the two trees only between these two sets. The expected number of parallel edges is then P i2A P j2B (di 1)(fj 1) (n 2) 2 = P i2A di 1 n 2 P j2B fj 1 n 2 = P n i=1 di 1 n 2 P n j=1 fj 1 n 2 = 1; since d i = 1 for all i2 A, f j = 1 for all j 2 B, and the sum of the degrees decreased by 1 isn 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. LetD = (d 1 ;:::;d n ) andF = (f 1 ;:::;f n ) be tree degree sequences such that each vertex is a leaf in at least one of them. ThenD andF have edge-disjoint tree realizations if and only ifd i < n 1 andf i < n 1 for alli. Proof. If max i fd i g = n 1 or max i ff i g = 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 indicesi 1 ;i 2 ;j 1 and j 2 such that i 1 ;i 2 2A and j 1 ;j 2 2B. Then there exists a pair of trees T 1 and T 2 such that both trees con- tain edges (v i1 ;v j1 ) and (v i2 ;v j2 ) andT 1 realizesD while T 2 realizes F . Indeed, the degree 1 vertices can be con- nected 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 againV =fv 1 ;:::;v n g. We need the following technical preliminary lemma. Lemma 7. Let D = (d 1 ;:::;d n ) be a tree degree se- quence, n > m > 2 and U =fv i j d i > 1g. Suppose V 1 ;:::;V m 1 are pairwise disjoint sets in L = V nU. Suppose further thatjUj > 1;jV 1 j > 1;:::;jV m 1 j > 1 andd i n m for alli. Then there is a treeT realizing D such that its restriction toU[V j is a non-star tree for allj. Proof. For any tree realizationT , its restriction toU[V j is a tree because outsideU there are only leaves. In the case jUj 4 we claim that there is a tree realizationT such that its restriction toU is not a star. Indeed, ifT restricted to U is a star centered atu2 U, then, by the degree bound, there is a leafw2L not connected tou. Letu 1 2U denote the unique neighbor ofw in the tree, and letu 2 be a third vertex ofU. Replacing edgesuu 2 andu 1 w by edgesu 1 u 2 anduw gives another tree realizationT whose restriction toU is not a star. For the casejUj = 2, letU =fv i ;v j g. Connect firstv i tov j . Nowd i +d j =n, sod i m andd j m. For each k m 1, connect one vertex ofV k tov i and another one tov j . The remaining leaves inL can be distributed easily: connect anyd i m of them tov i and the remainder tov j , giving the aimed tree realization. Finally supposeU =fv i ;v j ;v k g. We may also suppose that 2 d i d j d k . Connect firstv i andv j tov k . It is easy to connect vertices ofL toU in such a way that for each‘ m 1, at least one vertex ofV ‘ is connected to eitherv j orv k . Theorem 8. Let D 1 ;D 2 ;:::;D m be tree degree se- quences withD i = d i;1 ;d i;2 ;:::;d i;n such that each ver- tex is a leaf in all except at most one of them. Then D 1 ;D 2 ;:::;D m have edge-disjoint realizations if and only if max i;j fd i;j g n m. Proof. Necessity is clear asD 1 +D 2 + +D m is not graphical if max i;j fd i;j g>n m. The statement is trivial whenm = 1. Ifm = 2 then it is equivalent to Corollary 6, so we may supposem> 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. LetV i denote the subset of vertices on which the degrees inD i are larger than 1. Note thatfV 1 ;V 2 ;:::;V m g forms a subpartition of V andjV i j 2 for each i = 1;:::;m. For a degree sequenceD i , construct a trial tree ~ T i by using Lemma 7, which ensures that the subtree on verticesV i [V k is a non-star tree for anyk6=i. From the trial solution, which might contain several par- allel edges, a final solution is built in the following way. While there exists a pair of indexes (i;k) such that there Packing Tree Degree Sequences Informatica 43 (2019) 11–17 15 is one or more parallel edges between V i and V k , do the following. Let ~ T i;k denote the subtree of the tree ~ T i on vertices V i [V k and let ~ D i;k denote its degree sequence. By Corollary 6, ~ D i;k and ~ D k;i have edge-disjoint tree real- izations. Replace ~ T i;k and ~ T k;i by such realizations. This removes all parallel edges betweenV i andV k because ~ T j has no edge between these sets ifj6=i; j6=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 chal- lenge to estimate their number and/or sample almost uni- formly a solution. Here we prove the following theorem. Theorem 9. LetD = (d 1 ;:::;d n ) andF = (f 1 ;:::;f 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 dis- cussed, there are random trees with at least two parallel edges. The number of pair of trees containing parallel edges (v i1 ;v j1 ) and (v i2 ;v j2 ) such that d i1 ;d i2 > 1 and f j1 ;f j2 > 1 is (n 4)! (d i1 2)!(d i2 2)! Q k6=i1;i2 (d k 1)! (n 4)! (d j1 2)!(d j2 2)! Q k6=j1;j2 (f k 1)! : (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 num- ber of parallel edges. Therefore, the probability that two random trees will be edge-disjoint is at least (d i1 1)(d i2 1)(f j1 1)(f j2 1) (n 2) 2 (n 3) 2 : It follows from basic probabilistic arguments that an FPRAS algorithm can be designed based on this property. Indeed, let be the indicator variable that a random pair of trees are edge-disjoint realizations. Then the number of edge-disjoint realizations is E[ ] (n 2)! Q n k=1 (d i 1)! (n 2)! Q n k=1 (f i 1)! : Furthermore, we know that E[ ] (d i1 1)(d i2 1)(f j1 1)(f j2 1) (n 2) 2 (n 3) 2 : Uniformly distributed random trees with a prescribed de- gree sequence can be generated in polynomial time based on the fact that the probability that a given leaf is connected to a vertex with degreed i is d i 1 n 2 : A uniformly distributed tree can be generated by randomly selecting a neighbor of a given leaf, then generating a ran- dom tree for the remaining degree sequence. Equivalently, the trees with a prescribed degree sequence can be encoded by the Prüffer codes in which the indexi appears exactly d i 1 times. Uniformly generating such Prüffer codes is an elementary computational task. Therefore, random pair of trees can be generated in poly- nomial 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 . Indeed, if X i is 1 if the i th pair of random trees are edge-disjoint and 0 otherwise, then the random variable Y m := m X i=1 X i follows a binomial distribution with parameter p = E[ ] and expectationmE[ ]. The tails of the binomial distribu- tions can be bounded by the Chernoff’s inequality: P (Y m mp(1 )) exp 1 2p (mp mp(1 )) 2 m : This should be bounded by 2 (the other half error will go to the other tail) exp 1 2p (mp mp(1 )) 2 m 2 : (4) Solving Equation 4, we get m 2 log 2 p 2 : For the upper tail, we can also use the Chernoff’s inequal- ity, just replacing P with 1 p and the upper threshold mp(1 + ) withm mp(1 + ): P (Y m mp(1 + )) exp (m(1 p) (m mp(1+ ))) 2 2(1 p)m : Upper bounding this with 2 and solving the inequality, we get that m 2(1 p) log 2 p 2 2 : Since 1 p = O(n 4 ), the necessary number of samples is indeed polynomial with the size of the problem, 1 e and log( ). Furthermore, one sample can be generated in polynomial time, therefore this algorithm is indeed an FPRAS. 16 Informatica 43 (2019) 11–17 K. Bérczi et al. It is also well known that an FPAUS algorithm can be de- signed in this case. The FPAUS algorithm generate log( ) p pair of random trees. If any of them is an edge-disjoint re- alization, 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 inm number of samples is (1 p) m : This probability is not larger than . Indeed, (1 p) log( ) p ; since log( ) p log(1 p) log( ) because log(1 p) p: Namely, the algorithm generates realizations from a distri- bution which is the convex combination (1 0 )U + 0 , where 0 , U is the uniform distribution and is an arbitrary distribution. However, the variational distance of this distribution from the uniform one is d TV (U; (1 0 )U + 0 ) = 1 2 P x jU(x) ((1 0 )U(x) + 0 (x)j = 01 2 P x jU(x) (x)j 0 : 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( ), this algorithm is indeed and FPAUS. It remains an open question whether or not similar theo- rems 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 prob- lem is #P-complete. 5 A complexity result What can we say when only one of the two degree se- quences 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 D = (d 1;1 ;:::;d 1;n1 ); (d 2;1 ;:::;d 2;n2 ) and F = (f 1;1 ;:::;f 1;n1 ); (f 2;1 ;:::;f 2;n2 ) has an edge disjoint realization if and only if the simple degree sequence pair D 0 = (d 1;1 +n 1 1;:::;d 1;n1 +n 1 1;d 2;1 ;:::;d 2;n2 ) and F 0 = (f 1;1 ;:::;f 1;n1 ;f 2;1 +n 2 1;:::;f 2;n2 +n 2 1) has an edge-disjoint realization. Proof. If an edge-disjoint bipartite realization ofD andF 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 re- alization to get a (now non-bipartite) realization ofD 0 and F 0 . On the other hand, it is easy to see that any realization ofD 0 containsK n1 on the firstn 1 vertices, and any realiza- tion ofF 0 containsK n2 on the lastn 2 vertices. Given an edge-disjoint realization ofD 0 andF 0 , deletingK n1 from D 0 andK n2 fromF 0 yields an edge-disjoint realization of D andF . Claim 2. The degree sequence pairD = (d 1 ;:::;d n ) and F = (f 1 ;:::;f n ) has an edge-disjoint realization if and only if the degree sequence pairD 0 = (d 1 + 1;:::;d n + 1;n) andF 0 = (f 1 ;:::;f n ; 0) has an edge-disjoint real- ization. Proof. LetG 1 andG 2 be an edge-disjoint realization ofD and F . Then add a vertex v n+1 to G 1 , and connect it to all the other vertices to get a realization of D 0 . Add an isolated vertexv n+1 toG 2 to get a realization ofF 0 . These realizations of D 0 and F 0 are edge-disjoint. On the other hand, in any realization ofD 0 ,v n+1 is connected to all the other vertices. If edge-disjoint realizations of D 0 and F 0 are given, deletev n+1 from both realizations to get edge- disjoint realizations ofD andF . Claim 3. The degree sequence pairD = (d 1 ;:::;d n ) and F = (f 1 ;:::;f n ) has an edge-disjoint realization if and only if the degree sequence pair D 0 = (d 1 ;:::;d n ; 1; 1) andF 0 = (f 1 + 1;:::;f n + 1;n; 0) has an edge-disjoint realization. Proof. Any edge-disjoint realizationG 1 andG 2 ofD and F can be extended to an edge-disjoint realization ofD 0 and F 0 by adding two vertices v n+1 and v n+2 , and then con- nectingv n+1 to allv 1 ;:::;v n inG 2 and connectingv n+1 and v n+2 in G 1 . On the other hand, in any edge-disjoint realizationsG 0 1 andG 0 2 ofD 0 andF 0 ,v n+1 is connected to allv 1 ;:::;v n inG 0 2 , therefore,v n+1 must be connected to v n+2 in G 0 1 . Therefore deleting v n+1 and v n+2 yields an edge-disjoint realization ofD andF . Packing Tree Degree Sequences Informatica 43 (2019) 11–17 17 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 de- cide if two degree sequences have edge-disjoint realiza- tions such that one of the degree sequences does not have 0 degrees. Finally, Claim 3 can be used to iteratively trans- form anyD degree sequence (that already does not have a 0 degree) into a tree degree sequence. Indeed, in each step, we add two vertices toD and extend the sum of the degrees only by 2. Therefore in a polynomial number of steps, we get a degree sequenceD 0 in which the sum of the degrees is exactly twice the number of vertices minus 2. Therefore it follows that given any bipartite degree sequencesD and F , we can construct in polynomial time two simple degree sequencesD 0 andF 0 such thatD andF have edge-disjoint realizations if and only ifD 0 andF 0 have edge-disjoint re- alizations, furthermore,D 0 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 with- out 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 natu- ral question if a degree sequence and a tree sequence have edge-disjoint realizations if and only if their sum is graph- ical. 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 re- alizations. 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 de- gree vertices. However, when the two degree sequences have common high degree vertices then the problem re- mains open. References [1] Dürr, C., Guinez, F., Matamala, M.: Reconstruct- ing 3-colored grids from horizontal and vertical pro- jections is NP-hard. European Symposium on Algo- rithms, 776–787 (2009) [2] Erd˝ os, P.; Gallai, T. : Graphs with vertices of pre- scribed degrees (in Hungarian) Matematikai Lapok, 11: 264–274. (1960) [3] S.L. Hakimi: On the degrees of the vertices of a di- rected graph. J. Franklin Institute, 279(4):290–308. (1965) [4] V . Havel: A remark on the existence of finite graphs. (Czech), ˇ Casopis Pˇ est. 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) 18 Informatica 43 (2019) 11–17 K. Bérczi et al.