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$
6
  • $\begingroup$ Found the answer, it's NP-complete :( Here's a link to a paper researchgate.net/publication/… $\endgroup$
    – zaloo
    Jan 29, 2014 at 5:43
  • $\begingroup$ Could you explain how your question is related to the reference you give? $\endgroup$ Jan 29, 2014 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, 2014 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$ Jan 29, 2014 at 7:26
  • $\begingroup$ Okay, maybe i linked the wrong paper, but here's another. It's in the abstract $\endgroup$
    – zaloo
    Jan 29, 2014 at 7:33

2 Answers 2

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$
3
  • $\begingroup$ Damn this answered my question perfectly. Thanks! $\endgroup$
    – zaloo
    Jan 29, 2014 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, 2014 at 16:03
  • $\begingroup$ Nevermind, I found the paper on our uni database $\endgroup$
    – zaloo
    Jan 29, 2014 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 and acknowledge you have read our privacy policy.

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