Complexity of finding Exact Size Cut-Sets in Bipartite Graphs 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.
This is a partial answer that proves the NP-completeness of your problem, by a reduction from the EXACT-CUT problem for general graphs1. 

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&amp;\ge a(m+1-b)+b(m+1-a)\\
&amp;=(m+1)(a+b)+\frac{1}{2}(a-b)^2-\frac{1}{2}(a+b)^2\\
&amp;\ge(m+1)(a+b)-\frac{1}{2}(a+b)^2,
\end{align}
which implies $a+b&lt;1$ or $a+b&gt;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.



1 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.