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

<p>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.</p>

<p>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.</p>

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

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

<p>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, <a href="http://www.worldscientific.com/doi/abs/10.1142/S179383091250005X" rel="noreferrer">FPTAS for interval graphs</a> and <a href="http://link.springer.com/article/10.1007/s10878-012-9481-z" rel="noreferrer">5/4-approximation for grid graphs</a> (<a href="http://link.springer.com/chapter/10.1007/978-3-642-24983-9_19" rel="noreferrer">further improved to 7/6</a>).</p>

CC BY-SA 3.0
2014-01-29T15:51:01.803Z
Damn this answered my question perfectly. Thanks!
zaloo
CC BY-SA 3.0
2014-01-29T16:03:12.600Z
By chance do you have a link to the Chlebikova paper? I couldn't find any free copy online
zaloo
CC BY-SA 3.0
2014-01-29T19:42:51.817Z
Nevermind, I found the paper on our uni database
zaloo
CC BY-SA 3.0
2014-01-29T10:33:02.210Z
2014-01-29T18:49:27.020Z
2014-01-29T18:49:27.020Z
Bangye
<p>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.</p>

<p>This follows immediately from the the <a href="http://www.sciencedirect.com/science/article/pii/S0010465505004303" rel="nofollow noreferrer">NP-completeness</a> 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. </p>

<p>Interestingly, Yutsis graphs arise naturally in the quantum theory of angular momenta. <a href="https://physics.stackexchange.com/questions/80940/yutsis-graphs-in-quantum-theory">Here</a> I posted a related question on Physics SE. </p>

<p><strong>References</strong>:</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-01-29T15:29:35.530Z
2014-01-29T16:14:44.540Z
2017-04-13T12:40:17.207Z
Mohammad Al-Turkistany
<p>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 </p>

<p>\begin{equation}
|V_{1}| + |V_{2}| = |V|
\end{equation}
\begin{equation}
(|V_{1}| - |V|/2)^{2} \leq \epsilon^{2}, (|V_{2}| - |V|/2)^{2} \leq \epsilon^{2}
\end{equation}</p>

<p>and $V_{1}$ and $V_{2}$ should be disjoint.</p>

<p>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.</p>

CC BY-SA 3.0
2014-01-29T05:43:48.053Z
Found the answer, it's NP-complete :( Here's a link to a paper http://www.researchgate.net/publication/220152726_On_partitioning_a_graph_into_two_connected_subgraphs/file/e0b49522f16cd877f5.pdf
zaloo
CC BY-SA 3.0
2014-01-29T07:07:35.940Z
Could you explain how your question is related to the reference you give?
Igor Shinkar
CC BY-SA 3.0
2014-01-29T07:14:06.200Z
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
CC BY-SA 3.0
2014-01-29T07:26:22.017Z
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
CC BY-SA 3.0
2014-01-29T07:33:15.070Z
Okay, maybe i linked the wrong paper, but here's another. It's in the abstract
zaloo
CC BY-SA 3.0
2014-01-29T07:34:38.560Z
OH SHOOT i misread. Wow, I'm bad
zaloo
<graph-theory><partition-problem>
Partition a graph into 2 connected subgraphs
zaloo
# Partition a graph into 2 connected subgraphs

(Asked by: username_0 on 2014-01-29)

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

\begin{equation}
|V\_{1}| + |V\_{2}| = |V|
\end{equation}
\begin{equation}
(|V\_{1}| - |V|/2)^{2} \leq \epsilon^{2}, (|V\_{2}| - |V|/2)^{2} \leq \epsilon^{2}
\end{equation}

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.

**Tags:** graph-theory, partition-problem

> **Comments:**
> **username_0**: Found the answer, it's NP-complete :( Here's a link to a paper http://www.researchgate.net/publication/220152726_On_partitioning_a_graph_into_two_connected_subgraphs/file/e0b49522f16cd877f5.pdf  
> **username_1**: Could you explain how your question is related to the reference you give?  
> **username_0**: I thought I linked the pdf file. The paper has a proof for the NP-completeness of partitioning graphs into 2 connected sub graphs  
> **username_1**: 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.  
> **username_0**: Okay, maybe i linked the wrong paper, but here's another. It's in the abstract  
> **username_0**: OH SHOOT i misread. Wow, I'm bad  

---

## 2 answers

### Answer by username_2 on 2014-01-29. Score: 7 | Accepted answer

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](http://www.worldscientific.com/doi/abs/10.1142/S179383091250005X) and [5/4-approximation for grid graphs](http://link.springer.com/article/10.1007/s10878-012-9481-z) ([further improved to 7/6](http://link.springer.com/chapter/10.1007/978-3-642-24983-9_19)).

> **Comments:**
> **username_0**: Damn this answered my question perfectly. Thanks!  
> **username_0**: By chance do you have a link to the Chlebikova paper? I couldn't find any free copy online  
> **username_0**: Nevermind, I found the paper on our uni database  

---

### Answer by username_3 on 2014-01-29. Score: 2

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](http://www.sciencedirect.com/science/article/pii/S0010465505004303) 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](https://physics.stackexchange.com/questions/80940/yutsis-graphs-in-quantum-theory) 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.


---

