1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Discrete lizard ♦
    Feb 9 at 20:38
  • $\begingroup$ @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. $\endgroup$
    – J. Schmidt
    Feb 10 at 18:11

1 Answer 1

Reset to default
2
$\begingroup$

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$.

This problem is NP-hard even for bipartite graphs [1 Theorem 2.2]. For the approximation version of this problem, see this question on TCS.SE Partition a graph into 2 connected subgraphs.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice observation about my condition of the subgraphs needing to be trees can actually be relaxed into just needing to be connected. $\endgroup$
    – J. Schmidt
    Feb 10 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.