# Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input?

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?

• 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 :) Oct 31, 2015 at 14:43

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.

• Being $k \geq 3$ doesn't mean that $k$ is fixed? Oct 31, 2015 at 16:18
• @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 Jun 7, 2018 at 11:47