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

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

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

CC BY-SA 4.0
2018-08-13T16:06:10.913Z
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.
Elle Najt
CC BY-SA 4.0
2018-08-13T16:17:35.837Z
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!
Elle Najt
CC BY-SA 4.0
2018-08-13T18:17:27.903Z
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.)
Elle Najt
CC BY-SA 4.0
2018-08-14T05:58:03.347Z
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.
Mikhail Rudoy
CC BY-SA 4.0
2018-08-14T13:50:52.040Z
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.
Elle Najt
CC BY-SA 4.0
2018-08-15T07:19:37.773Z
You're right. I wasn't aware of that particular bijection. I had intuitively figured out the bijection between even subgraphs and edge cuts, and instead of extending this to a bijection between simple cycles and bonds, I just imposed the extra condition that the graph is cubic (since in a cubic graph every even subgraph is simple).
Mikhail Rudoy
CC BY-SA 4.0
2018-08-15T13:51:08.760Z
Okay. Thanks for this discussion, the ideas here were really useful for me. :)
Elle Najt
CC BY-SA 4.0
2018-07-27T07:44:34.307Z
2018-07-27T07:44:34.307Z
Mikhail Rudoy
<p>Here is a straightforward reduction from the max-cut problem: </p>

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

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

CC BY-SA 4.0
2018-07-27T08:42:09.727Z
2018-07-27T08:58:34.103Z
2018-07-27T08:58:34.103Z
Saeed
<p>Let $G$ be a connected graph.</p>

<p>Consider the problem of finding a partition $G = A \cup B$ into <em>connected</em> 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.?</p>

<p>The situation without connectedness is MAX-CUT. The situation when only $A$ is required to be connected has been studied here: <a href="https://arxiv.org/abs/1507.00648" rel="noreferrer">https://arxiv.org/abs/1507.00648</a></p>

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

CC BY-SA 4.0
2021-12-07T16:52:52.793Z
maybe you can try to use greedy algorithm, contract edge with smallest weight each time.
Tianqi Ma
CC BY-SA 4.0
2021-12-07T17:30:06.617Z
Here's a paper about a closely related problem: [Approximation Algorithms for Connected Maximum Cut and Related Problems, by
Hajiaghayi et al](https://arxiv.org/abs/1507.00648).
Neal Young
<cc.complexity-theory><reference-request><graph-algorithms><approximation-algorithms><randomized-algorithms>
Max cut problem between two connected subgraphs
Elle Najt
# Max cut problem between two connected subgraphs

(Asked by: username_0 on 2018-07-26)

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.

**Tags:** cc.complexity-theory, reference-request, graph-algorithms, approximation-algorithms, randomized-algorithms

> **Comments:**
> **username_1**: maybe you can try to use greedy algorithm, contract edge with smallest weight each time.  
> **username_2**: Here's a paper about a closely related problem: [Approximation Algorithms for Connected Maximum Cut and Related Problems, by Hajiaghayi et al](https://arxiv.org/abs/1507.00648).  

---

## 2 answers

### Answer by username_3 on 2018-07-27. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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!  
> **username_0**: 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.)  
> **username_3**: 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.  
> **username_0**: 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.  
> **username_3**: You're right. I wasn't aware of that particular bijection. I had intuitively figured out the bijection between even subgraphs and edge cuts, and instead of extending this to a bijection between simple cycles and bonds, I just imposed the extra condition that the graph is cubic (since in a cubic graph every even subgraph is simple).  
> **username_0**: Okay. Thanks for this discussion, the ideas here were really useful for me. :)  

---

### Answer by username_4 on 2018-07-27. Score: 5

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.


---

