VERTEX COVER PROBLEM

(Redirected from Vertex cover)
In computer science, the 'vertex cover problem' or 'node cover problem' is an NP-complete problem in complexity theory, and was one of Karp's 21 NP-complete problems.

A ''vertex cover'' of an undirected graph $G\; =\; (V,\; E)$ is a subset $V\text{'}$ of the vertices of the graph which contains at least one of the two endpoints of each edge:
:.
In the graph at the right, {1,3,5,6} is an example of a vertex cover. {2,4,5} is another, smaller vertex cover.
The vertex cover problem is the optimization problem of finding a vertex cover of minimum size in a graph. The problem can also be stated as a decision problem:
:INSTANCE: A graph $G$ and a positive integer $k$.
:QUESTION: Is there a vertex cover of size $k$ or less for $G$?
Vertex cover is NP-complete, which means it is unlikely that there is an efficient algorithm to solve it. NP-completeness can be proven by reduction from 3-satisfiability 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]
Vertex cover is closely related to Independent Set problem: $V\text{'}$ is a vertex cover iff its complement, $V\; setminus\; V\text{'}$, 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$.
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
:
ight)
for a given $V\; geq\; 2$ ^[3] but cannot be approximated within a factor of 1.3606 for any sufficiently large vertex degree unless P=NP.^[4]
A brute force algorithm to find a vertex cover in a graph is to choose some vertex and recursively branch into two cases: either take this vertex into the vertex cover, or all its neighbors. This algorithm is exponential in $k$, but not in the size of the graph, i.e., vertex cover is fixed-parameter tractable with respect to $k$.
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.

Contents

See also

References

External links

See also

★ covering (graph theory)

References

★ , Michael R. Garey and David S. Johnson, , , W.H. Freeman, 1979, ISBN 0-7167-1045-5 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.

★ A compendium of NP optimization problems
1.
2. The rectilinear Steiner tree problem is NP-complete, , M. R., Garey, SIAM Journal on Applied Mathematics, 1977
3. George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
4. 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").

External links

★ Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring