Vertex cover problem

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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.

1 Definition
2 Tractability
3 Fixed-Parameter Tractability
4 Approximability
5 See also
6 References
- 6.1 Further References
7 External links

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 $\bar 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

Blue vertices form a vertex cover.
3-sat: {A, B', C}

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 $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)}$ .^[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|}} \right)$

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

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.

References

^ 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
^ Garey, M. R.; D. S. Johnson (1977). "The rectilinear Steiner tree problem is NP-complete". SIAM Journal on Applied Mathematics 32 (4): 826–834. doi:10.1137/0132071.
^ Flum, J.; Grohe, M. (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3.
^ 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").