<p>Is <span class="math-container">$k$</span> considered a constant in this context? If so, the problem can be trivially solved in linear time. If <span class="math-container">$|E| \geq 2k$</span> then the answer is yes (there is always a cut of size at least <span class="math-container">$|E|/2$</span>, since a random cut has size <span class="math-container">$|E|/2$</span> in expectation), and otherwise this problem can be solved in <span class="math-container">$O(2^{4k})$</span> rounds by enumerating over all possible cuts on vertices that have edges.</p>
<p>If <span class="math-container">$k$</span> can be arbitrarily dependent on <span class="math-container">$n$</span>, then this is NP-complete, because max-cut can be reduced to it.</p>

CC BY-SA 4.0
2021-01-30T18:51:55.450Z
2021-01-30T18:51:55.450Z
user3209423940248
<p>I have to show that for every integer <span class="math-container">$k$</span>, the problem whether the vertices of input graph can be partitioned into two sets such that there are a least <span class="math-container">$k$</span> edges between the sets can be solved in polynomial time.</p>
<p>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?</p>

CC BY-SA 4.0
2021-01-30T20:34:54.063Z
You should better ask such questions to your teacher.
Gamow
<np-hardness><max-cut>
Partition vertices of graph into two sets such that there are at least $k$ edges between sets
Majstro
# Partition vertices of graph into two sets such that there are at least $k$ edges between sets

(Asked by: username_0 on 2021-01-30)

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?

**Tags:** np-hardness, max-cut

> **Comments:**
> **username_1**: You should better ask such questions to your teacher.  

---

## 1 answers

### Answer by username_2 on 2021-01-30. Score: 3

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.


---

