Vertex cover problem

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.

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 smallest vertex cover 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 $$ar 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.

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 [Citation|first1=M. R.|last1=Garey|author1-link=Michael R. Garey|author2-link=David S. Johnson|last2=Johnson|first2=D. S.|last3=Stockmeyer|first3=L.|contribution-url=http://portal.acm.org/citation.cfm?id=803884|contribution=Some simplified NP-complete problems|title=Proceedings of the sixth annual ACM symposium on Theory of computing|pages=47–63|year=1974] and even in planar graphs of degree at most 3 [cite journal|first=M. R.|last=Garey|authorlink=Michael R. Garey|coauthors=D. S. Johnson|title=The rectilinear Steiner tree problem is NP-complete|journal=SIAM Journal on Applied Mathematics|pages=826–834|year=1977|volume=32|number=4|doi=10.1137/0132071] .

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.

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)}.cite book
author = Flum, J.
coauthors = Grohe, M.
year = 2006
title = Parameterized Complexity Theory
publisher = Springer
url = http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0
isbn = 978-3-540-29952-3]

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| ight)

for a given $$V geq 2 [George Karakostas. [http://www.cas.mcmaster.ca/~gk/papers/vc.pdf A better approximation ratio for the Vertex Cover problem] . ECCC Report, TR04-084, 2004.] but cannot be approximated within a factor of 1.3606 for any sufficiently large vertex degree unless P=NP. [I. Dinur and S. Safra. [http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf 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").]

Although finding the minimum-size vertex cover is equivalent to finding the maximum-size independent set, as described above, the two problems are not equivalent in the sense of approximation. The Independent Set problem has no constant-factor approximation unless P=NP.

See also

* covering (graph theory)
* Hitting set, a natural generalization of vertex cover to hypergraphs

References

Further References

* A1.1: GT1, pg.190.
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 35.1, pp.1024–1027.

External links

* [http://www.nada.kth.se/~viggo/wwwcompendium/node10.html A compendium of NP optimization problems]
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring]