# Is it NP-hard to check whether for a $k$ there exist both a Cut and a Bisection of value $k$?

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

• Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.
Jun 30 '21 at 21:21
• 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.
– D.W.
Jun 30 '21 at 21:22

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