4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented Oct 23, 2018 at 8:49
  • $\begingroup$ @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? $\endgroup$
    – allrtaken
    Commented Oct 23, 2018 at 14:24
  • 1
    $\begingroup$ Cross post of cs.stackexchange.com/questions/98914/… (two days earlier) $\endgroup$
    – Neal Young
    Commented Oct 29, 2018 at 13:19

1 Answer 1

Reset to default
3
$\begingroup$

The problem of bipartite exact cuts is NP-Complete, as shown here by a reduction from exact cuts in general graphs.

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.