Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

Question

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.

Answer 1

This is a partial answer that proves the NP-completeness of your problem, by a reduction from the EXACT-CUT problem for general graphs¹.

Given an instance $(G=(V,E),k)$ of the EXACT-CUT problem (that asks whether there is a cut of size $k$ in the graph $G$), we construct a new graph $G'$ as follows.

• For each vertex $v\in V$, construct vertices $v_0^0,\ldots,v_m^0,v_0^1,\ldots,v_m^1$ as well as edges $(v_i^0, v_j^1)$ for all $i,j\in\{0,\ldots,m\}$ (so that they form a biclique). Denote $V_v=\{v_0^0,\ldots,v_m^0,v_0^1,\ldots,v_m^1\}$.

• For each edge $(u,v)\in E$, construct two edges $(u_0^0, v_0^1)$ and $(u_0^1, v_0^0)$.

Here $m=2k$. Note $G'$ is a bipartite graph.

Now we can see if $(A,B)$ is a cut of size $k$ in $G$, then $(\cup_{v\in A}V_v,\cup_{v\in B}V_v)$ is a cut of size $2k$ in $G'$.

On the other hand, suppose there is a cut $(A',B')$ of size $2k$ in $G'$. Now consider a vertex $v$. Assume $|A'\cap\{v_0^0,\ldots,v_m^0\}|=a$ and $|A'\cap\{v_0^1,\ldots,v_m^1\}|=b$, then we have \begin{align} m=2k&\ge a(m+1-b)+b(m+1-a)\\ &=(m+1)(a+b)+\frac{1}{2}(a-b)^2-\frac{1}{2}(a+b)^2\\ &\ge(m+1)(a+b)-\frac{1}{2}(a+b)^2, \end{align} which implies $a+b<1$ or $a+b>2m+1$, i.e. $a=b=0$ or $a=b=m+1$. This means all vertices in $V_v$ must belong to the same cut-set. Hence $(\{v\mid V_v\subseteq A'\}, \{v\mid V_v\subseteq B'\})$ is a cut of size $k$ in $G$.

Now we have shown that there is a cut of size $k$ in $G$ if and only if there is a cut of size $2k$ in $G'$, which concludes the proof of the NP-completeness of the EXACT-CUT problem on bipartite graphs.

---

_{¹ Your reasoning for the NP-completeness of the EXACT-CUT problem is incorrect because you used a Turing reduction while a many-one reduction is required. However, it is not hard to find such a polynomial-time many-one reduction.}

Answer 2

This is an $NP$-complete problem to which EXACT-COVER-BY-$3$-SETS (X3C) can be reduced.

Given an instance of X3C, construct the standard bipartite graph (i.e. the collection of $3$-sets forms one side, and the ground set forms the other side).

To prevent any cut that takes some and leaves some from the ground set, we do like this. Create a large amount of dummy vertices (on the side of the collection of $3$-sets, of course). For each element, connect it to all of these dummy vertices. Now, if we separate any pair of elements then for each dummy vertex, we need to take into the cut-set exactly one edge. And, this will blow up the total count for the cut-set.

Note that the set of dummy vertices are common for every element.

So, all the ground set needs to be on one side of the cut.

As a result, there can be at most one dummy vertex that resides on the opposite side of the ground set.

The value $k=\mid U\mid$ should now take care of the rest for us. Nearly done!

What if one takes only one dummy vertex on one side and every other vertex on the other side.

Just, similarly create a large enough amount of dummy elements. And connect each dummy element to all the dummy $3$-sets.

The argument that all ground set needs to be on one side still holds. And, one can take the exact cover on one side and all other vertices on the other side to construct a cut-set of size $k$ as required. Now, really done, yet? Not yet.

We need to make sure the chosen $3$-sets are pairwise-disjoint.

To do this, we need to utilize a restricted version of X3C. In this restricted version, each $3$-set intersects with exactly $6$ other $3$-sets. So for each pair of overlapping $3$-sets, connect both to a large enough number $M$ of dummy vertices (not elements, not $3$-sets, of course). $M$ can be taken as a large (still polynomially in magnitude) that is coprime to $\mid U \mid$, $m$ (number of $3$-sets). Now, connect each of the latest added dummy vertex to all the dummy $3$-sets above. This serves as guarantee that every last added dummy vertex is in the safe side. Finally, choose some $M'$ coprime to $M$ (and everything else) from the dummy vertices between each intersecting pair to connect them to other $3$-sets outside of the pair

Surely, we need to update $k$ accordingly as $k:=k+6M\frac{k}3+6M'(\frac{k}3-1)\frac{k}3$. DONE!

---

Note that the number of dummy $3$-sets must be much larger than $M$ (and so, certainly also $M'$).