Vertex cover

From Wikipedia, the free encyclopedia

In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory.

The minimum vertex cover problem can be formulated as a half-integral linear program whose dual linear program is the maximum matching problem.

Covering-Packing Dualities
Covering problems	Packing problems
Minimum Set Cover	Maximum Set Packing
Minimum Vertex Cover	Maximum Matching
Minimum Edge Cover	Maximum Independent Set

Contents 1 Definition 1.1 Examples 1.2 Properties 2 Computational problem 2.1 ILP formulation 2.2 Exact evaluation 2.2.1 Fixed-parameter tractability 2.3 Approximate evaluation 2.3.1 Inapproximability 3 Vertex cover in hypergraphs 3.1 Fixed-parameter tractability 3.2 Hitting set and set cover 4 Notes 5 References

[edit] Definition

Formally, a vertex cover of a graph G is a set of vertices C such that each edge of G is incident to at least one vertex in C. The set C is said to cover the edges of G. The following figure shows examples of vertex covers in two graphs (the set C is marked with red).

A minimum vertex covering is a vertex covering of smallest possible size. The vertex covering number τ is the size of a minimum vertex covering. The following figure shows examples of minimum vertex coverings in two graphs.

[edit] Examples

• The set of all vertices is a vertex cover.
• The complement of an independent set is a vertex cover.
• The endpoints of a maximal matching form a vertex cover.
• The complete bipartite graph K_m,n has vertex covering number min(m, n).

[edit] Properties

• The number of vertices of a graph is equal to its vertex covering number plus the size of a maximum independent set (Gallai 1959).

[edit] Computational problem

The minimum 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 C for G of size k.

If the problem is stated as a decision problem, it is called the vertex cover problem:

INSTANCE: Graph G and positive integer k.

QUESTION: Is there a vertex cover C for G of size at most k?

The vertex cover problem is an NP-complete problem: it was one of Karp's 21 NP-complete problems. It is often used in computational complexity theory to prove that another problem is NP-hard.

[edit] ILP formulation

Assume that every vertex has an associated cost of . The (weighted) minimum vertex cover problem can be formulated as the following integer linear program.^[1]

minimize			(minimize the total cost)
subject to		for all	(cover every edge of the graph)
		for all .	(every vertex is either in the vertex cover or not)

This ILP belongs to the more general class of ILPs for covering problems. The integrality gap of this ILP is 2, so its relaxation gives a factor-2 approximation algorithm for the minimum vertex cover problem. Furthermore, the linear programming relaxation of that ILP is half-integral, that is, there exists an optimal solution with for all

[edit] Exact evaluation

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 or, as Karp did, by reduction from the clique problem. Vertex cover remains NP-complete even in cubic graphs^[2] and even in planar graphs of degree at most 3^[3].

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] Fixed-parameter tractability

A brute force algorithm can solve the problem in time 2^O(k)n^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. One algorithmic technique that works here is called bounded search tree algorithm, and its idea is to repeatedly choose some vertex and recursively branch, with two cases at each step: place either the current vertex or all its neighbours into the vertex cover. Under reasonable complexity-theoretic assumptions, namely the exponential time hypothesis, this running time cannot be improved to 2^o(k)n^O(1).

For planar graphs, however, a vertex cover of size k can be found in time , i.e., the problem is subexponential fixed-parameter tractable. This algorithm is again optimal, in the sense that, under the exponential time hypothesis, no algorithm can solve vertex cover on planar graphs in time .^[4]

[edit] Approximate evaluation

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. Put otherwise, we find a maximal matching M with a greedy algorithm and construct a vertex cover C that consists of all endpoints of the edges in M. In the following figure, a maximal matching M is marked with red, and the vertex cover C is marked with blue.

The set C constructed this way is a vertex cover: suppose that an edge e is not covered by C; then M ∪ {e} is a matching and e ∉ M, which is a contradiction with the assumption that M is maximal. Furthermore, if e = {u,v} ∈ M, then any vertex cover – including an optimal vertex cover – must contain u or v (or both); otherwise the edge e is not covered. That is, an optimal cover contains at least one endpoint of each edge in M; in total, the set C is at most 2 times as large as the optimal vertex cover.

This simple algorithm was discovered independently by Fanica Gavril and Mihalis Yannakakis.^[5]

More involved techniques show that there are approximation algorithms with a slightly better approximation factor. For example, an approximation algorithm with an approximation factor of is known.^[6]

[edit] Inapproximability

No better constant-factor approximation algorithm than the above one is known. The minimum vertex cover problem is APX-complete, that is, it cannot be approximated arbitrarily well unless P=NP. Dinur and Safra proved, using techniques from the PCP theorem, that minimum vertex cover cannot be approximated within a factor of 1.3606 for any sufficiently large vertex degree unless P=NP.^[7]

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 an approximation-preserving way: The Independent Set problem has no constant-factor approximation unless P=NP.

[edit] Vertex cover in hypergraphs

Vertex cover has a natural generalization to hypergraphs which is often just called vertex cover for hypergraphs but which is also known under the names hitting set and, in a more combinatorial context, transversal. Even more, the notions of hitting set and set cover are equivalent.

Formally, let H=(V,E) be a hypergraph with vertex set V and hyperedge set E. Then a set S ⊆ V is called hitting set of H if, for all edges e ∈ E, it holds S ∩ e ≠ ∅. The computational problems minimum hitting set and hitting set are defined as in the case of graphs.

Note that we get back the case of vertex covers for simple graphs if the maximum size of the hyperedges is 2. If that size is restricted to d, the problem of finding a minimum d-hitting set permits a d-approximation algorithm.

[edit] Fixed-parameter tractability

For the hitting set problem, different parameterizations make sense.^[8] The hitting set problem is W[2]-complete for the parameter OPT, that is, it is unlikely that there is an algorithm that runs in time f(OPT)n^O(1) where OPT is the cardinality of the smallest hitting set. The hitting set problem is fixed-parameter tractable for the parameter OPT + d, where d is the size | e | of the largest edge of the hypergraph. More specifically, there is an algorithm for hitting set that runs in time d^OPTn^O(1).

[edit] Hitting set and set cover

The Hitting Set Problem is equivalent to the Set cover problem: An instance of set cover can be viewed as an arbitrary bipartite graph, with sets represented by vertices on the left, the universe represented by vertices on the right, and edges representing the inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the left-vertices using a minimum subset of the right vertices. Converting from one problem to the other is therefore achieved by interchanging the two sets of vertices.

[edit] Notes

1. ^ Vazirani (2001, pp. 122-123)
2. ^ 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 
3. ^ 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. 
4. ^ Flum & Grohe (2006)
5. ^ Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), Combinatorial Optimization: Algorithms and Complexity, Dover , p. 432, mentions both Gavril and Yannakakis. Garey, Michael R.; Johnson, David S. (1979 [2003]), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman , p. 134, cites Gavril.
6. ^ George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
7. ^ 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").
8. ^ Flum & Grohe (2006)

[edit] References

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. Cambridge, Mass.: MIT Press and McGraw-Hill. pp. 1024–1027. ISBN 0-262-03293-7. 
• Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0. 
• 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.
• Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
• Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8. 
• Weisstein, Eric W. "Vertex Cover" From MathWorld.