Packing tree degree sequences

Abstract

A degree sequence $D=(d_1,\dots, d_n)$ is a series of non-ne\-ga\-tive integers. A degree sequence is graphical if there exists a vertex labeled graph $G$ in which the degree of vertex $v_i$ is exactly $d_i$ for $i=1,\dots,n$. The graph $G$ is called a realization of $D$. The \emph{edge-disjoint realization problem} is the following: given a $c \times n$ degree matrix $D=\{(d_{1,1},\dots, d_{1,n} ),$ $(d_{2,1},\dots,d_{2,n} ),\dots, (d_{c,1},\dots, d_{c,n})\}$, in which each row of the matrix is a graphical degree sequence, decide if there exists pairwise edge-disjoint realizations of these degree sequences on the same vertex set $V=\{v_1,v_2,\dots,v_n\}$. Such set of edge-disjoint graphs is called a realization of the degree matrix. A realization can also be presented as an edge colored simple graph, in which the edges with a given color form a realization of the degree sequence in a given row of the degree matrix.

It is known that the edge-disjoint realization problem is $\NP$-complete even if the number of rows is three and the degrees on each vertex sum up to $n-1$, that is, when a decomposition of the complete graph is required into three subgraphs with prescribed degrees. Moreover, the problem is also $\NP$-complete when the number of rows is two and the sum of the degrees on some of the vertices is less than $n-1$. However, special cases that are computationally tractable are also of interest. A classical result of Kundu \cite{kundutree} shows that deciding if two \emph{tree degree sequences} have edge-disjoint realizations is in $\P$.

Motivated by the aforementioned result, we consider special cases of the problem for two tree degree sequences. We show that if there is no node which have degree one in both degree sequences (that is, the requested trees do not share a common leaf node) 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. This theorem can be extended to more trees: we 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, i.e., in every column of the degree matrix there is at most one entry which is greater than one.

We also consider the following variant of the edge-disjoint realization problem: given two graphical degree sequences $D_1$ and $D_2$ such that $D_2$ is a tree degree sequence, decide if there exists edge-disjoint realizations of $D_1$ and $D_2$ where the realization of $D_2$ does not need to be a tree. We show that this problem is already $\NP$-complete.

Counting, or just estimating the number of distinct realizations of degree sequences is challenging in general. 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.