1
$\begingroup$

Input: An undirected, unweighted graph $G=(V,E)$.

A cut is defined as a partition $V=A\dot\cup B$.

A bisection is defined as a partition $V=A\dot\cup B$ with $|A|=|B|$ if $|V|$ is even (or $|A|= |B|+1$ if $|V|$ is odd).

We define the value of a cut/bisection $V=A\dot\cup B$ as $E[A,B]$, i.e. as the number of edges between the partitions.

Question:

Is it NP-hard to solve the following problem:
Given an integer $k$, do there exist both a Cut and a Bisection of value $k$?

The problem is in NP, because given a cut and a bisection, we can efficiently check whether both have value $k$.

I'm also wondering whether there are somewhat general techniques that help one decide the NP-hardness of a problem which is more or less two NP-hard problems slapped together by an equality.


Literature:

NP-completeness of Max-Cut: DOI:10.1016/0304-3975(76)90059-1

NP-completeness of Vertex Bisection: DOI=10.1.1.154.5438

$\endgroup$
2
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – D.W.
    Jun 30 '21 at 21:21
  • $\begingroup$ The title of your question does not match the problem listed in the body of your question. I encourage you to edit the question to improve the title. Thank you. $\endgroup$
    – D.W.
    Jun 30 '21 at 21:22
2
$\begingroup$

Your problem is equivalent to the following:

Given an integer $k$, does there exist a bisection of value $k$?

In particular, every bisection is a cut, so if there exists a bisection of value $k$, then there also exists a cut of value $k$; if there does not exist a bisection of value $k$, then there does not exist both a cut and a bisection of value $k$.

This revised problem is NP-complete -- it follows from the NP-hardness of the maximum bisection problem. So, your problem is NP-complete, too (since it is the same problem).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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