6
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ @Raphael , I tried Articulation point algorithm but it does not give fully disconnected graph. $\endgroup$
    – user7711
    Apr 15 '13 at 5:01
10
$\begingroup$

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[1]$-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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Juho
    Apr 13 '13 at 15:19
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Apr 14 '13 at 18:22
  • $\begingroup$ 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). $\endgroup$
    – user742
    May 8 '13 at 14:19
  • $\begingroup$ 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. :) $\endgroup$
    – Pål GD
    Jun 12 '13 at 9:02

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.