# Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?

I'd like to decide whether, given a connected graph $$G = (V, E)$$ and an integer $$k$$ as input, $$G$$ admits two vertex-disjoint subgraphs $$T_1 = (V_1, E_1)$$ and $$T_2 = (V_2, E_2)$$ such that $$T_1$$ and $$T_2$$ are trees, $$V_1 \cup V_2 = V$$ (so in some way they are spanning), and $$|V_1 - V_2| \leq k$$ (they aren't too different in size).

Some graphs, such as perfect binary trees or Hamiltonian graphs, do admit such balanced spanning trees ($$k=o(1)$$), whereas others do not, such as star graphs ($$k = n - 2$$).

Is this NP-hard? Is it already NP-hard when fixing $$k=0$$? Also, is the smallest $$k$$ for which such trees can be found a known parameter, like maybe balanced vertex-disjoint spanning tree distance'' or something? I did not find any information on vertex-disjoint spanning trees like this, I always end up with an article on edge-disjoint spanning trees (which each individually are spanning).

EDIT: vertex-arboricity (resp. equitable vertex-arboricity) seems quite close, but here one aims to partition the vertices such that their induced subgraph is a forest (resp. forests of the same size). They don't seem interested in the exact number of partitions (whereas I fix it to two) and I'm not interested in induced subgraphs or forests.

• I wonder if there are any $2$-connected graphs that do not admit balanced spanning trees for $k\leq 1$. These graphs seem to have a lot of freedom in choosing the pair of trees, although I'm not sure if it's enough. If all $2$-connected graphs have a balanced pair of spanning trees, then it seems likely there is a polynomial time algorithm. If not, I think an example may give some insight into why the problem may be hard. Feb 9, 2023 at 20:38
• @Discretelizard that got me thinking! In the answer's cited paper, a result of Gyori and Lovasz (Theorem 1.1) implies a 2-connected graph always has such a balanced pair of spanning trees. I suppose this implies that it is only hard to decide if 1-connected graphs admit such trees, huh. Feb 10, 2023 at 18:11

For $$k = 0$$, this problem is equivalent to the problem known as Balanced Connected Vertex 2-Partition problem: given a graph $$G = (V,E)$$, find a partition of the vertex set $$V = V_1 \cup V_2$$ such that $$|V_1| = |V_2| = |V|/2$$ and the induced subgraphs $$G[V_1]$$ and $$G[V_2]$$ are connected. Note that if an induced subgraph $$G[V_i]$$ is connected then we can take a spanning tree of it as $$T_i$$.