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?
Asked By : user7711
Answered By : Pål GD
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11281
0 comments:
Post a Comment
Let us know your responses and feedback