1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy