1
$\begingroup$

I wonder whether the following problem is a well-studied NP-hard problem?

Get a graph $G$ and a number $k$, we partition the graph $G$ into two components where each component should have at most $k$ vertices and the number of edges in the cut is minimal.

In other words, is the mini-cut problem with the vertex budget constraint NP-hard?

Thanks.

Improve this question
$\endgroup$
3
  • $\begingroup$ How many vertices does $G$ have and are there lower bounds on the vertices in each component? $\endgroup$
    – Manfred Weis
    Commented Mar 4, 2020 at 4:43
  • $\begingroup$ No, there are not lower bounds on the vertices in each component. You can assume that the number of vertices of $G$ is $n$. $\endgroup$
    – Polaris
    Commented Mar 4, 2020 at 21:42
  • $\begingroup$ Since we're looking for a bipartition, upper bounds on the part sizes are exactly the same as lower bounds. $\endgroup$
    – Ben Barber
    Commented Mar 14, 2020 at 9:42

1 Answer 1

Reset to default
1
$\begingroup$

Min-cut with bounded part sizes is the same as max-cut with bounded part sizes on the complement. Given any graph $H$ for which we would like to know the max-cut, form a new graph $G$ by adding $|H|$ isolated vertices. Then the max-cut of $G$ with bounded part sizes is the max-cut of $H$, with the part sizes balanced out using the isolated vertices. So max-cut can be reduced to max-cut (or min-cut) with bounded part sizes, and your problem in NP-hard.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Could you elaborate your first claim? I imagine something like that to be true, but don't see the exact correspondence. $\endgroup$
    – smapers
    Commented Apr 13, 2020 at 12:50
  • 1
    $\begingroup$ @smpapers, you're right, that only works if the parts are balanced rather than bounded -- if the partition is into parts of size as equal as possible then they're equivalent because the total number of possible crossing edges is fixed. Happily the reduction I sketch is to balanced max-cut, and so balanced min-cut, which is a special case of bounded min-cut (so the general case is still NP-hard). $\endgroup$
    – Ben Barber
    Commented Apr 15, 2020 at 13:42
  • $\begingroup$ Great, I agree. $\endgroup$
    – smapers
    Commented Apr 15, 2020 at 13:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .