7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Found the answer, it's NP-complete :( Here's a link to a paper researchgate.net/publication/… $\endgroup$ – zaloo Jan 29 '14 at 5:43
  • $\begingroup$ Could you explain how your question is related to the reference you give? $\endgroup$ – Igor Shinkar Jan 29 '14 at 7:07
  • $\begingroup$ I thought I linked the pdf file. The paper has a proof for the NP-completeness of partitioning graphs into 2 connected sub graphs $\endgroup$ – zaloo Jan 29 '14 at 7:14
  • 2
    $\begingroup$ 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. $\endgroup$ – Igor Shinkar Jan 29 '14 at 7:26
  • $\begingroup$ Okay, maybe i linked the wrong paper, but here's another. It's in the abstract $\endgroup$ – zaloo Jan 29 '14 at 7:33
7
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

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

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