6
$\begingroup$

Let $G$ be a connected graph.

Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known about this, e.g. complexity, approximation, randomized algorithms, etc.?

The situation without connectedness is MAX-CUT. The situation when only $A$ is required to be connected has been studied here: https://arxiv.org/abs/1507.00648

I'm also interested in the case when $A$ and $B$ are required to be of roughly equal size.

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
2
$\begingroup$

One specific case of your problem is to partition $G$ into $A$ and $B$ such that the induced subgraphs on those two vertex sets are trees. We will refer to this task as partitioning a graph into two trees. This is a specific case of your problem because maximizing the number of edges that are cut corresponds to minimizing the number of edges that are not cut, and given that $A$ and $B$ are connected, the minimum possible number of edges that are not cut is $(|A| - 1) + (|B| - 1) = |G| - 2$ in the case that both $A$ and $B$ are trees.

For a planar cubic graph $G'$, the dual $G$ of $G'$ can be partitioned into two trees if and only if $G'$ has a Hamiltonian cycle. In particular, if $H$ is a Hamiltonian cycle in $G'$, then the corresponding partition of the vertices of $G$, aka faces of $G'$, into the ones interior to $H$ and the ones exterior to $H$ is a partition into two trees.

Thus, if you further restrict your problem to the case of partitioning the dual of a planar cubic graph into two trees, the specific case you are left with is equivalent to finding a Hamiltonian Cycle in a planar cubic graph. Since that task is NP-hard, so is this special case of your problem. And if a special case of your problem is NP-hard, then your problem as a whole is also NP-hard.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I'm not sure I really buy your first paragraph. For example, if G is the compete graph, it's impossible to partition the vertices so that the induced subgraphs are both trees. I agree that maximizing the number of edges cut corresponds to minimizing the number of edges not cut. I think the mistake is in the assertion that the only constraint on the minimum number not cut is given by the requirement that the induced subgraphs be connected. In particular, for the complete graph , the actual constraint on min not cut is much larger. $\endgroup$
    – Elle Najt
    Commented Aug 13, 2018 at 16:06
  • $\begingroup$ What I think is true is that if the graph can be partitioned into two trees, then this corresponds to a max cut. So you show that decision problem " is there a connected cut with G - 2 edges not cut" is equivalent to Hamiltonian cycle. And so if we could solve connected max cut, we would know if there was a connected cut that achieved the bound coming from a partition into two trees, and we would be able to answer Hamiltonian cycle. I think I see your point, I'm just being slow. Thanks! $\endgroup$
    – Elle Najt
    Commented Aug 13, 2018 at 16:17
  • $\begingroup$ Remaining question: why the assumption that G is cubic? I think the duality between Hamiltonian cycles and partitions into trees is true for all planar graphs. (The bijection is between minimal cycles of G and partitions into connected induced subgraphs of the dual of G.) $\endgroup$
    – Elle Najt
    Commented Aug 13, 2018 at 18:17
  • $\begingroup$ Imagine a (non-simple) cycle in a planar graph that uses all 4 edges at a degree 4 vertex. The dual of that cycle could also be a partition of the dual graph into two trees. On the other hand, if every vertex has degree 3, then you can pretty easily show that exactly two edges at each vertex will be used. $\endgroup$
    – Mikhail Rudoy
    Commented Aug 14, 2018 at 5:58
  • $\begingroup$ non simple cycles will partition the dual into more than two components. In general the bijection is between simple cycles (minimal even subgraphs) and bonds of the dual (cut sets that partition it into two connected components). This is corollary 2.12 in Erickson's notes on planar graphs (first result in Google - it's not easy for me to copy the link on my phone). Hamiltonian cycles are simple. (Maybe we're taking past each other?) I don't think cubic is a necessary assumption for your reduction. $\endgroup$
    – Elle Najt
    Commented Aug 14, 2018 at 13:50
5
$\begingroup$

Here is a straightforward reduction from the max-cut problem:

Take any graph and add two new vertices $u,v$ and connect them to every other vertex with weight 0 and connect them to each other by a very very big weight edge. In an optimal solution to the above problem $u$ is in one partition and $v$ in the other (this also ensures that each part is a connected component), hence an algorithm that solves this problem in the new graph, could solve the max-cut problem in the original graph and vice versa.

P.S: I supposed we can have edge weights as otherwise a similar argument works however instead of adding vertices we add two long paths (each of length $n^2$), for $i\le n$ we connect the $i$'th vertex of the path $P_j$ (for $j\in \{0,1\}$) to the $i$'th vertex of the graph and we connect all vertices of $P_1$ to the all vertices of $P_2$. Then again in an optimal solution path $P_1$ is on one side and path $P_2$ on the other side.

Improve this answer
$\endgroup$

Your Answer

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