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.
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.
NP-completeness of Max-Cut: DOI:10.1016/0304-3975(76)90059-1
NP-completeness of Vertex Bisection: DOI=10.1.1.154.5438