Vertex cover problem

From Wikipedia, the free encyclopedia

In computer science, the vertex cover problem or node cover problem is an NP-complete problem and was one of Karp's 21 NP-complete problems. It is often used in complexity theory to prove NP-hardness of more complicated problems.

Contents

[edit] Definition

A vertex cover for an undirected graph G = (V,E) is a subset S of its vertices such that each edge has at least one endpoint in S. In other words, for each edge ab in E, one of a or b must be an element of S.

Example: In the graph on the right, {1,3,5,6} is an example of a vertex cover of size 4. However, it is not a smallest vertex cover since there exist vertex covers of size 3, such as {2,4,5} and {1,2,4}.

The vertex cover problem is the optimization problem of finding a vertex cover of size k in a given graph.

INSTANCE: Graph G.
OUTPUT: Smallest number k such that there is a vertex cover S for G of size k.

Equivalently, the problem can be stated as a decision problem:

INSTANCE: Graph G and positive integer k.
QUESTION: Is there a vertex cover S for G of size at most k?

Vertex cover is closely related to the Independent Set problem. A set of vertices S is a vertex cover if and only if its complement \bar S = V \setminus S is an independent set. It follows that a graph with n vertices has a vertex cover of size k if and only if the graph has an independent set of size n − k. In this sense, the two problems are dual to each other.

[edit] Tractability

The decision variant of the vertex cover problem is NP-complete, which means it is unlikely that there is an efficient algorithm to solve it exactly. NP-completeness can be proven by reduction from 3-satisfiability (see image on the right) or, as Karp did, by reduction from the clique problem. Vertex cover remains NP-complete even in cubic graphs[1] and even in planar graphs of degree at most 3[2].

For bipartite graphs, the equivalence between vertex cover and maximum matching described by König's theorem allows the bipartite vertex cover problem to be solved in polynomial time.

[edit] Fixed-Parameter Tractability

Despite the fact that vertex cover is NP-complete, a brute force algorithm can solve the problem in time 2^{\mathcal O(k)} n^{\mathcal O(1)}. Vertex cover is therefore fixed-parameter tractable, and if we are only interested in small k, we can solve the problem in polynomial time. The strategy of the brute force algorithm is to choose some vertex and recursively branch, with two cases at each step: place either the current vertex or all its neighbors into the vertex cover. Under reasonable complexity-theoretic assumptions, this running time cannot be improved to 2^{o(k)} n^{\mathcal O(1)}.

For planar graphs, however, a vertex cover of size k can be found in time 2^{\mathcal O(\sqrt{k})} n^2, i.e., the problem is subexponential fixed-parameter tractable. This algorithm is again optimal, in the sense that, under the same complexity-theoretic assumptions, no algorithm can solve vertex cover on planar graphs in time 2^{o(\sqrt{k})} n^{\mathcal O(1)}.[3]

[edit] Approximability

One can find a factor-2 approximation by repeatedly taking both endpoints of an edge into the vertex cover, then removing them from the graph. No better constant-factor approximation is known; the problem is APX-complete, i.e., it cannot be approximated arbitrarily well. More precisely, minimum vertex cover is known to be approximable within

2 - \Theta \left( \frac{1}{\sqrt{\log |V|}} \right)

for a given V \geq 2 [4] but cannot be approximated within a factor of 1.3606 for any sufficiently large vertex degree unless P=NP.[5]

[edit] See also

[edit] References

  1. ^ Garey, M. R.; Johnson, D. S. & Stockmeyer, L. (1974), “Some simplified NP-complete problems”, Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47-63 
  2. ^ Garey, M. R.; D. S. Johnson (1977). "The rectilinear Steiner tree problem is NP-complete". SIAM Journal on Applied Mathematics 32: 826-834. doi:10.1137/0132071. 
  3. ^ Flum, J.; Grohe, M. (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. 
  4. ^ George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
  5. ^ I. Dinur and S. Safra. On the Hardness of Approximating Minimum Vertex-Cover. Annals of Mathematics, 162(1):439-485, 2005. (Preliminary version in STOC 2002, titled "On the Importance of Being Biased").

[edit] External links