4
$\begingroup$

As you know a set of edges whose removal leaves $k$ connected components is called a $k$-cut. The minimum $k$-cut problem asks for a minimum weight $k$-cut.

For $k=2$ this problem is P.

Vazirani in his book says for any fixed $k$ when $3 \le k$ it is NP-hard and When $k$ is specified as part of the input this problem is also NP-hard.

I would like to know what difference does it make when $k$ is specified as part of the input? and why is it NP-hard in this case?

$\endgroup$
1
  • $\begingroup$ I already saw that before. I guess this is in contradiction with Vazirani book. But I will take care of that when I figure out why for not specified $k$ it is NP-hard :) $\endgroup$
    – M a m a D
    Oct 31 '15 at 14:43
4
$\begingroup$

First, be careful what Vazirani actually says. On page 38, it is written that:

"The minimum $k$-cut problem is polynomial time solvable for fixed $k$; however, it is NP-hard if $k$ is specified as part of the input."

(In particular, the claim you make about being NP-hard for any fixed $k \geq 3$ holds for a different problem, namely minimum weight multiway cut). Indeed, Wikipedia states this is the case as well: for any fixed $k$, you can solve the minimum $k$-cut problem in $O(n^{k^2})$ time. In other words, when $k$ is fixed, you have polynomially many ways of removing $k$ edges. So why does it matter if something is part of the input or fixed then?

When $k$ is fixed, it is not part of the input. The problem is this:

(Minimum $k$-cut.) Input: A graph $G$. Question: Is there a $k$-cut?

So the problem is defined for every fixed value of $k$. We have minimum 2-cut, minimum 3-cut, minimum 4-cut, and so on. In contrast, the problem could be this:

(Minimum cut.) Input: A graph $G$, an integer $k$. Question: Is there a $k$-cut?

Now, it is possible for $k$ to depend crucially on the size of the graph. This way a naive brute-force won't give you a polynomial time algorithm. Another example is given in this question of ours in the context of finding cliques.

$\endgroup$
2
  • $\begingroup$ Being $k \geq 3$ doesn't mean that $k$ is fixed? $\endgroup$
    – M a m a D
    Oct 31 '15 at 16:18
  • $\begingroup$ @Noone Being $k \geq 3$ is NP-hard, then this means that k is NP-hard for fixed k. This follows that it is NP-hard for k equal n. Now, Vizirnai's make this difference of the two; because usually to prove hardness for fixed is different than prove hardness for any any k; and this is one way to show Strongly NP-hard. I suggest reading Garey and Johnson textbook $\endgroup$
    – user777
    Jun 7 '18 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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