[Solved]: Is set cover still NP-complete if you have a given k?

Problem Detail: 

Set cover is NP-complete given an arbitrary set $U$, a set $S$ of subsets of $U$, and an integer $k$. However, what if $k$ is always a constant 3? Is that problem still NP-complete?

Asked By : TheJKFever

Answered By : Luke Mathieson

No.

Like many $NP$-complete problems, fixing the solution size gives a polynomial-time algorithm. In this case, we're looking for a group of at most $(k=)3$ sets $s_{1}$, $s_{2}$ and $s_{3}$ from $S$ such that $s_{1}\cup s_{2} \cup s_{3} = U$, so we can simply try every set of 3, which gives a $O(|S|^{3})$ algorithm because there's only $\binom{|S|}{3}$ groups of three sets taken from $S$, and in general, for every fixed $k$, an $O(|S|^{k})$ algorithm.

This is true for many other problems, like Dominating Set, Vertex Cover, Independent Set, $k$-Clique etc. etc. These all have $O(n^{k})$ brute force algorithms. Expressed in Parameterized Complexity terms, they're all in the class $XP$ (in fact, for all of these, they're in $W[P]$) when the parameter is the solution size¹.

Note the contrast with problems like k-Coloring, which is $NP$-complete for every fixed $k \geq 3$. The best algorithms for problems like these have running times more like $O(k^{n})$ - the relationship between $k$ and $n$ is reversed to what we had before. Again in Parameterized Complexity terminology, such things are $para$-$NP$-complete, and don't have (non-uniform $XP$ algorithms unless $P = NP$.

Footnotes

1. $XP$ is the class of all parameterized problems that have a polynomial time algorithm for every fixed value of the parameter, also called "slicewise polynomial". $W[P]$ is the class of problems that have a nondeterministic algorithm that runs in $f(k)n^{O(1)}$ time with at most $h(k)\log n$ nondeterministic steps for some $h$, where $k$ is the parameter - we can remove the nondeterminism and get a $O(n^{O(h(k))})$ algorithm for some function $g$, through the same approach of trying all possible solution certificates.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42161