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 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]