# Partition a graph into 2 connected subgraphs

I'm stumped on a sub problem that I'm working on for my thesis. I need to be able to partition a graph into 2 connected subgraphs of almost equal size. So if there are $m$ vertices in $G$, subgraphs $G_{1}$ and $G_{2}$ should have

$$|V_{1}| + |V_{2}| = |V|$$ $$(|V_{1}| - |V|/2)^{2} \leq \epsilon^{2}, (|V_{2}| - |V|/2)^{2} \leq \epsilon^{2}$$

and $V_{1}$ and $V_{2}$ should be disjoint.

Anyone know a quick way to compute if this exists and what the partition should be? I know that partitioning in general is NP-hard but I didn't know if it was for this special case.

• Found the answer, it's NP-complete :( Here's a link to a paper researchgate.net/publication/… – zaloo Jan 29 '14 at 5:43
• Could you explain how your question is related to the reference you give? – Igor Shinkar Jan 29 '14 at 7:07
• I thought I linked the pdf file. The paper has a proof for the NP-completeness of partitioning graphs into 2 connected sub graphs – zaloo Jan 29 '14 at 7:14
• In the reference you give there two subgraphs must contain some specified sets of vertices, and there is no requirement that the partition is balanced. I don't see how your question reduces to this. – Igor Shinkar Jan 29 '14 at 7:26
• Okay, maybe i linked the wrong paper, but here's another. It's in the abstract – zaloo Jan 29 '14 at 7:33

The problem you asked is the unweighted version of the Balance Connected 2-Partition ($BCP_2$).

For unweighted case, any 2-connected graph can be partitioned into two connected subgraphs whose numbers of vertices differ by at most one. A simple algorithm uses st-numbering. For any 2-connected graph, we can label the vertices by $[1...n]$ such that any vertex has simultaneously a neighbor with smaller label and a neighbor with larger label. Let $V_1=\{1...n/2\}$ and $V_2=V-V_1$. It can be easily shown that both $V_1$ and $V_2$ induce connected subgraphs.

However, when there are cut vertices, the problem is NP-hard because it is equivalent to the weighted $BCP_2$. The transformation is as follows. Let $v$ be a cut vertex and $H$ be the maximum connected component in $G-v$. We shrink all components other than $H$ into $v$ and the weight of $v$ is given by the weight of the vertices combined in $v$. Repeat this process and we can obtain a weighted 2-connected graph.

It can be easily realized that there exists a graph such that the minimum part contains only $n/3$ vertices in any 2-partition.

For $BCP_2$, the currently best approximation algorithm is due to Chlebikova (I hope that it is not out of date):

Approximating the maximally balanced connected partition problem in graphs, Information Processing Letters, 60:225--230, 1996. The approximation ratio is 4/3. For some special graphs, there are better results. For example, FPTAS for interval graphs and 5/4-approximation for grid graphs (further improved to 7/6).

• Damn this answered my question perfectly. Thanks! – zaloo Jan 29 '14 at 15:51
• By chance do you have a link to the Chlebikova paper? I couldn't find any free copy online – zaloo Jan 29 '14 at 16:03
• Nevermind, I found the paper on our uni database – zaloo Jan 29 '14 at 19:42

It is $NP$-complete to determine the existence of a partition of the vertex set $V$ of cubic graph into two vertex-induced trees of equal size.

This follows immediately from the the NP-completeness of deciding whether a cubic graph is Yutsis graph ( Yutsis graphs are also known as dual Hamiltonian cubic graphs). Jaeger proved that a graph $G(V, E)$ is dual Hamiltonian if and only if it has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce a tree.

Interestingly, Yutsis graphs arise naturally in the quantum theory of angular momenta. Here I posted a related question on Physics SE.

References:

1- F. Jaeger, On vertex-induced forests in cubic graphs, Proceedings 5th Southeastern Conference, Congressus Numerantium (1974) 501–512.

2- D. Van Dyck, G. Brinkmann, V. Fack, B.D. McKay, To be or not to be Yutsis: algorithms for the decision problem, Computer Physics Communications 173 (2005) 61–70.