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 Failed to parse (Missing texvc executable; please see math/README to configure.): G = (V, E)

is a subset Failed to parse (Missing texvc executable; please see math/README to configure.): S
of its vertices such that each edge has at least one endpoint in Failed to parse (Missing texvc executable; please see math/README to configure.): 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, Failed to parse (Missing texvc executable; please see math/README to configure.): \{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 Failed to parse (Missing texvc executable; please see math/README to configure.): \{2,4,5\}
and Failed to parse (Missing texvc executable; please see math/README to configure.): \{1,2,4\}

.

The vertex cover problem is the optimization problem of finding a vertex cover of size Failed to parse (Missing texvc executable; please see math/README to configure.): k

in a given graph.

INSTANCE: Graph Failed to parse (Missing texvc executable; please see math/README to configure.): G

.

OUTPUT: Smallest number Failed to parse (Missing texvc executable; please see math/README to configure.): k

such that there is a vertex cover Failed to parse (Missing texvc executable; please see math/README to configure.): S
for Failed to parse (Missing texvc executable; please see math/README to configure.): G
of size Failed to parse (Missing texvc executable; please see math/README to configure.): k

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

INSTANCE: Graph Failed to parse (Missing texvc executable; please see math/README to configure.): G

and positive integer Failed to parse (Missing texvc executable; please see math/README to configure.): k

.

QUESTION: Is there a vertex cover Failed to parse (Missing texvc executable; please see math/README to configure.): S

for Failed to parse (Missing texvc executable; please see math/README to configure.): G
of size at most Failed to parse (Missing texvc executable; please see math/README to configure.): k

?

Vertex cover is closely related to the Independent Set problem. A set of vertices Failed to parse (Missing texvc executable; please see math/README to configure.): S

is a vertex cover if and only if its complement Failed to parse (Missing texvc executable; please see math/README to configure.):  \bar S = V \setminus S
is an independent set. It follows that a graph with Failed to parse (Missing texvc executable; please see math/README to configure.): n
vertices has a vertex cover of size Failed to parse (Missing texvc executable; please see math/README to configure.): k
if and only if the graph has an independent set of size Failed to parse (Missing texvc executable; please see math/README to configure.): 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^[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.

Fixed-Parameter Tractability

Despite the fact that vertex cover is NP-complete, a brute force algorithm can solve the problem in time Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{\mathcal O(k)} n^{\mathcal O(1)}.

Vertex cover is therefore fixed-parameter tractable, and if we are only interested in small Failed to parse (Missing texvc executable; please see math/README to configure.): 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 Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{o(k)} n^{\mathcal O(1)} .

For planar graphs, however, a vertex cover of size Failed to parse (Missing texvc executable; please see math/README to configure.): k

can be found in time Failed to parse (Missing texvc executable; please see math/README to configure.): 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 Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{o(\sqrt{k})} n^{\mathcal O(1)} .^[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

Failed to parse (Missing texvc executable; please see math/README to configure.): 2 - \Theta \left( \frac{1}{\sqrt{\log |V|}} \right)

for a given Failed to parse (Missing texvc executable; please see math/README to configure.): V \geq 2

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

See also

• covering (graph theory)
• 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.
• 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.

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. 
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").

External links

• A compendium of NP optimization problems
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloringde:Glossar Graphentheorie#Knotenüberdeckung

he:בעיית כיסוי קודקודים
ja:頂点被覆問題