How to find the minimum number of vertices whose removal make the graph disjoint

Given a graph $G = (V,E)$.

Is there any algorithm which finds the minimum number of vertices to be removed from $G$ so that every vertex in the graph becomes disjoint, i.e., every vertex is disconnected from every other vertex?

• @Raphael , I tried Articulation point algorithm but it does not give fully disconnected graph. Apr 15 '13 at 5:01

This problem is known as vertex cover. The minimum vertex cover of a graph is the smallest number of vertices adjacent to every edge. The complement of a vertex cover is an independent set.

Given a graph $G = (V,E)$ and $k \in \mathbb{N}$, the problem of finding whether $G$ has a vertex cover of size at most $k$ is NP-complete. However, it admits a polynomial kernel and is thus fixed-parameter tractable. It also admits a quite easy and nice $2^k n^{O(1)}$ branching algorithm:

Pick any edge $e = vu$: Either $v$ goes to the vertex cover, or $u$ goes to the vertex cover. Make a recursive algorithm which picks $e$, removes $v$ from the graph and calls itself recursively with $k-1$ as parameter. If that fails, proceed by removing $u$. If that fails as well, can conclude that there is no such vertex cover.

There are also nice 2-approximation algorithms for this problem.

Ps. this is maybe one of the "easier" NP-hard problems. So if you want to implement it, you're in good luck despite the hardness.

Pps. if you want to find an independent set (also known as stable set) of size at least $k$, you are out of luck, as that problem is $W$-complete, see the W-hierarchy. However, there is an $O(2^{0.288n})$ exact algorithm solving independent set using Measure and Conquer by Fomin et al. (SODA 2006) (doi=10.1.1.79.831). A quick caveat here: Many are confused upon first reading why a trivial reduction does not show that independent set is in FPT as well. The answer here lies in the fact that a reduction will set the new parameter $k' = O(n-k)$, i.e., the new parameter will depend on $n$ as well.

• Also knowing something about the structure of the input graph might make the problem tractable. For example, the vertex cover problem is easy for trees.
– Juho
Apr 13 '13 at 15:19
• Yes, and more generally it is solvable in linear time for chordal graphs. It also has a PTAS on planar graphs. That vertex cover is solvable in polytime on chordal graphs means that independent set is as well. Apr 14 '13 at 18:22
• Just as a side note, is also $O(2^{\sqrt k}\cdot n^{O(1)})$ time solvable in graphs of H-Minor free for some fixed graph H. (which contains all of bounded genus and planar, ...) and the algorithm is actually easy (bidimentionality theory).
– user742
May 8 '13 at 14:19
• I'm not sure I would call any algorithm relying on the graph minors theorem "actually easy". It's nothing you simply go ahead and implement. :) Jun 12 '13 at 9:02