I have to show that for every integer $k$, the problem whether the vertices of input graph can be partitioned into two sets such that there are a least $k$ edges between the sets can be solved in polynomial time.

The only solution I can think of is that it is a maximum-cut problem a therefore it is NP-complete problem. So my question is am I on good track that it is a instance of maximum-cut problem or am I wrong?

  • $\begingroup$ You should better ask such questions to your teacher. $\endgroup$
    – Gamow
    Jan 30 at 20:34

Is $k$ considered a constant in this context? If so, the problem can be trivially solved in linear time. If $|E| \geq 2k$ then the answer is yes (there is always a cut of size at least $|E|/2$, since a random cut has size $|E|/2$ in expectation), and otherwise this problem can be solved in $O(2^{4k})$ rounds by enumerating over all possible cuts on vertices that have edges.

If $k$ can be arbitrarily dependent on $n$, then this is NP-complete, because max-cut can be reduced to it.


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