Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
