The question is clear from the title. What is the complexity of the following decision problem:
Input: An undirected graph $G(V, E)$
Output: $\mathrm{YES}$ if $G$ can be decomposed into two edge-disjoint spanning trees, $\mathrm{NO}$ otherwise
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
Your problem is in $\mathrm{NP} \cap \mathrm{co}$-$\mathrm{NP}$.
First, it is obviously in $\mathrm{NP}$. The verifier receives the certificate consisting of two edge-disjoint spanning trees that consumes all the edges in $\mathrm{E}$
Second, by Tutte & Nash-Williams theorem [1], your problem is also in $\mathrm{co}$-$\mathrm{NP}$. The co-nondeterministic machine guesses any partition $\mathrm{P}$ of $\mathrm{V}$ and check that $|\mathrm{E}_\mathrm{P}(\mathrm{G})| \geq 2(|\mathrm{P}| - 1)$. Also, it must check that $|\mathrm{E}| = 2(|\mathrm{V}| - 1)$ to be sure that the tree packing of the above theorem is indeed a decomposition by trees.
[1] Tomas Kaiser, A short proof of the tree-packing theorem, https://arxiv.org/pdf/0911.2809.pdf
answered Sep 2 '18 at 4:04
