<p>The problem of bipartite exact cuts is NP-Complete, as shown <a href="https://cs.stackexchange.com/q/98976">here</a> by a reduction from exact cuts in general graphs.</p>

CC BY-SA 4.0
2018-10-24T08:41:17.380Z
2018-10-24T08:41:17.380Z
allrtaken
<p>I am interested in the problem of deciding if a cut-set of a given size <span class="math-container">$k$</span> (i.e. the number of edges crossing the partitions is <span class="math-container">$k$</span>) exists in a given bipartite graph (both the graph and <span class="math-container">$k$</span> are part of the input). Note that this is different from the problems of MINCUT and MAXCUT which simply ask to find the minimum and maximum sized cutsets.</p>

<p>For general graphs, the MINCUT problem can be solved in polynomial time while the MAXCUT problem is NP-Hard. It follows that deciding if a cutset of a particular size exists in a general graph is also NP-Hard since we could use it to find the maximum sized cutset.</p>

<p>For bipartite graphs however, the MAXCUT problem is trivial -- all the edges in the graph constitute the MAXCUT. Moreover, if it helps, I think I can show that for bipartite graphs, the edge - complement of a cutset is also a cutset. That is if <span class="math-container">$E_c\subseteq E$</span> is a cutset of a bipartite graph <span class="math-container">$G=(U\cup V,E)$</span> then <span class="math-container">$E−E_c$</span> is also a cutset of <span class="math-container">$G$</span>.</p>

<p>However, I have not been able to determine if deciding if a cutset of some size <span class="math-container">$k$</span> exists is in P or is NP-Complete or something else. If it is Np-Complete, is there a family of graphs for which it is in P? Any pointers will be helpful.</p>

CC BY-SA 4.0
2018-10-23T08:49:44.027Z
Bipartite MAXCUT is NP-hard when edges have weights chosen from the set {-1,1} (Roth and Viswanathan, 2008). Let $G$ be such a graph. Form $G'$ from $G$ where edges with weight -1 are turned into M parallel edges, for sufficiently large M and edges of weight 1 are kept as they are. Now being able to decide if $G'$ has a cut of a given size allows one to determine the weight of a maximum weight cut in $G$.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2018-10-23T14:24:55.260Z
@KristofferArnsfeltHansen Thanks for the reply. While your solution looks correct, I was wondering if it would be possible to have a construction without parallel edges. Introducing 2M vertices with one edge between each pair is an option, but in that case I'm not sure we'd be able to enforce the  mapping between exact cuts in G' and +1-1 cuts in G. In particular, it may be possible that in a cut of G', only some of the M new edges are included, whereas for your construction, it was crucial that all M edges are included or none at all, if I followed it correctly. Any ideas?
allrtaken
CC BY-SA 4.0
2018-10-29T13:19:45.210Z
Cross post of https://cs.stackexchange.com/questions/98914/complexity-of-finding-exact-size-cut-sets-in-bipartite-graphs/98976#98976 (two days earlier)
Neal Young
<cc.complexity-theory><graph-theory><np-complete><polynomial-time><max-cut>
Complexity of finding Exact Size Cut-Sets in Bipartite Graphs
allrtaken
# Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

(Asked by: username_0 on 2018-10-23)

I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part of the input). Note that this is different from the problems of MINCUT and MAXCUT which simply ask to find the minimum and maximum sized cutsets.

For general graphs, the MINCUT problem can be solved in polynomial time while the MAXCUT problem is NP-Hard. It follows that deciding if a cutset of a particular size exists in a general graph is also NP-Hard since we could use it to find the maximum sized cutset.

For bipartite graphs however, the MAXCUT problem is trivial -- all the edges in the graph constitute the MAXCUT. Moreover, if it helps, I think I can show that for bipartite graphs, the edge - complement of a cutset is also a cutset. That is if $E\_c\subseteq E$ is a cutset of a bipartite graph $G=(U\cup V,E)$ then $E−E\_c$ is also a cutset of $G$.

However, I have not been able to determine if deciding if a cutset of some size $k$ exists is in P or is NP-Complete or something else. If it is Np-Complete, is there a family of graphs for which it is in P? Any pointers will be helpful.

**Tags:** cc.complexity-theory, graph-theory, np-complete, polynomial-time, max-cut

> **Comments:**
> **username_1**: Bipartite MAXCUT is NP-hard when edges have weights chosen from the set {-1,1} (Roth and Viswanathan, 2008). Let $G$ be such a graph. Form $G'$ from $G$ where edges with weight -1 are turned into M parallel edges, for sufficiently large M and edges of weight 1 are kept as they are. Now being able to decide if $G'$ has a cut of a given size allows one to determine the weight of a maximum weight cut in $G$.  
> **username_0**: @KristofferArnsfeltHansen Thanks for the reply. While your solution looks correct, I was wondering if it would be possible to have a construction without parallel edges. Introducing 2M vertices with one edge between each pair is an option, but in that case I'm not sure we'd be able to enforce the  mapping between exact cuts in G' and +1-1 cuts in G. In particular, it may be possible that in a cut of G', only some of the M new edges are included, whereas for your construction, it was crucial that all M edges are included or none at all, if I followed it correctly. Any ideas?  
> **username_2**: Cross post of https://cs.stackexchange.com/questions/98914/complexity-of-finding-exact-size-cut-sets-in-bipartite-graphs/98976#98976 (two days earlier)  

---

## 1 answers

### Answer by username_0 on 2018-10-24. Score: 3 | Accepted answer

The problem of bipartite exact cuts is NP-Complete, as shown [here](https://cs.stackexchange.com/q/98976) by a reduction from exact cuts in general graphs.


---

