Vertex cover problem

From Wikipedia, the free encyclopedia

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'$ of the vertices of the graph which contains at least one of the two endpoints of each edge:

$V' \subseteq V: \forall \{a, b\} \in E : a \in V' \or b \in V'$ .

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. As shown by Garey and Johnson in 1974, vertex cover remains NP-complete even in cubic graphs and even in planar graphs of degree at most 6.

Vertex cover is closely related to Independent Set problem: $V'$ is a vertex cover iff its complement, $V \setminus V'$ , 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

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

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

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.

[edit] See also

covering (graph theory)

[edit] References

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, 1979.
Preeti Patil & Sangita Patil. (Lecturer in Vartak Polytechnic) A Guide to the Theory of NP-Completeness. BPB & Co., Mumbai, 2004.
M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems. Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63. 1974.
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.
Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.1: GT1, pg.190.
A compendium of NP optimization problems

^ George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
^ 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").