Vertex cover

Example graph that has a vertex cover comprising 2 vertices (bottom), but none with fewer.

In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations. It 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.

Vertex cover problems have been generalized to hypergraphs, see Vertex cover in hypergraphs .

Definition

Examples of vertex covers

Examples of minimum vertex covers

Formally, a vertex cover ${\displaystyle V'}$ of an undirected graph ${\displaystyle G=(V,E)}$ is a subset of ${\displaystyle V}$ such that ${\displaystyle uv\in E\Rightarrow u\in V'\lor v\in V'}$, that is to say it is a set of vertices ${\displaystyle V'}$ where every edge has at least one endpoint in the vertex cover ${\displaystyle V'}$. Such a set is said to cover the edges of ${\displaystyle G}$. The upper figure shows two examples of vertex covers, with some vertex cover ${\displaystyle V'}$ marked in red.

A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number ${\displaystyle \tau }$ is the size of a minimum vertex cover, i.e. ${\displaystyle \tau =|V'|}$. The lower figure shows examples of minimum vertex covers in the previous graphs.

Examples

• The set of all vertices is a vertex cover.
• The endpoints of any maximal matching form a vertex cover.
• The complete bipartite graph ${\displaystyle K_{m,n}}$ has a minimum vertex cover of size ${\displaystyle \tau (K_{m,n})=\min\{\,m,n\,\}}$.

Properties

• A set of vertices is a vertex cover if and only if its complement is an independent set.
• Consequently, the number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set. ^[1]

Computational problem

The minimum vertex cover problem is the optimization problem of finding a smallest vertex cover in a given graph.

INSTANCE: Graph ${\displaystyle G}$

OUTPUT: Smallest number ${\displaystyle k}$ such that ${\displaystyle G}$ has a vertex cover of size ${\displaystyle k}$.

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

INSTANCE: Graph ${\displaystyle G}$ and positive integer ${\displaystyle k}$.

QUESTION: Does ${\displaystyle G}$ have a vertex cover of size at most ${\displaystyle 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 as a starting point for NP-hardness proofs.

ILP formulation

Assume that every vertex has an associated cost of ${\displaystyle c(v)\geq 0}$. The (weighted) minimum vertex cover problem can be formulated as the following integer linear program (ILP). ^[2]

minimize	${\displaystyle \textstyle \sum _{v\in V}c(v)x_{v}}$			(minimize the total cost)
subject to	${\displaystyle x_{u}+x_{v}\geq 1}$	for all ${\displaystyle \{u,v\}\in E}$		(cover every edge of the graph),
	${\displaystyle x_{v}\in \{0,1\}}$	for all ${\displaystyle v\in V}$.		(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 ${\displaystyle 2}$, so its relaxation (allowing each variable to be in the interval from 0 to 1, rather than requiring the variables to be only 0 or 1) gives a factor-${\displaystyle 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 for which each entry ${\displaystyle x_{v}}$ is either 0, 1/2, or 1. A 2-approximate vertex cover can be obtained from this fractional solution by selecting the subset of vertices whose variables are nonzero.

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 for arbitrary graphs. 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 ^[3] and even in planar graphs of degree at most 3. ^[4]

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.

For tree graphs, an algorithm finds a minimal vertex cover in polynomial time by finding the first leaf in the tree and adding its parent to the minimal vertex cover, then deleting the leaf and parent and all associated edges and continuing repeatedly until no edges remain in the tree.

Fixed-parameter tractability

An exhaustive search algorithm can solve the problem in time 2^kn^O(1), where k is the size of the vertex cover. 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. The algorithm for solving vertex cover that achieves the best asymptotic dependence on the parameter runs in time ${\displaystyle O(1.2738^{k}+(k\cdot n))}$. ^[5] The klam value of this time bound (an estimate for the largest parameter value that could be solved in a reasonable amount of time) is approximately 190. That is, unless additional algorithmic improvements can be found, this algorithm is suitable only for instances whose vertex cover number is 190 or less. Under reasonable complexity-theoretic assumptions, namely the exponential time hypothesis, the running time cannot be improved to 2^o(k), even when ${\displaystyle n}$ is ${\displaystyle O(k)}$.

However, for planar graphs, and more generally, for graphs excluding some fixed graph as a minor, a vertex cover of size k can be found in time ${\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}$, i.e., the problem is subexponential fixed-parameter tractable. ^[6] 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 ${\displaystyle 2^{o({\sqrt {k}})}n^{O(1)}}$. ^[7]

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. ^[8]

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 ${\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}$ is known. ^[9] The problem can be approximated with an approximation factor ${\displaystyle 2/(1+\delta )}$ in ${\displaystyle \delta }$ - dense graphs. ^[10]

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. Using techniques from the PCP theorem, Dinur and Safra proved in 2005 that minimum vertex cover cannot be approximated within a factor of 1.3606 for any sufficiently large vertex degree unless P = NP. ^[11] Later, the factor was improved to ${\displaystyle {\sqrt {2}}-\epsilon }$ for any ${\displaystyle \epsilon >0}$. ^[12] Moreover, if the unique games conjecture is true then minimum vertex cover cannot be approximated within any constant factor better than 2. ^[13]

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.

Pseudocode

APPROXIMATION-VERTEX-COVER(G)C=∅E'=G.EwhileE'≠∅:let(u,v)beanarbitraryedgeofE'C=C∪{u,v}removefromE'everyedgeincidentoneitheruorvreturnC

^{[14] [15]}

Applications

Vertex cover optimization serves as a model for many real-world and theoretical problems. For example, a commercial establishment interested in installing the fewest possible closed circuit cameras covering all hallways (edges) connecting all rooms (nodes) on a floor might model the objective as a vertex cover minimization problem. The problem has also been used to model the elimination of repetitive DNA sequences for synthetic biology and metabolic engineering applications. ^{[16] [17]}

See also

• Dominating set

Notes

1. Gallai 1959.
2. Vazirani 2003 , pp. 121–122
3. Garey, Johnson & Stockmeyer 1974
4. Garey & Johnson 1977; Garey & Johnson 1979, pp. 190 and 195.
5. Chen, Kanj & Xia 2006
6. Demaine et al. 2005
7. Flum & Grohe (2006 , p. 437)
8. Papadimitriou & Steiglitz 1998, p. 432, mentions both Gavril and Yannakakis. Garey & Johnson 1979, p. 134, cites Gavril.
9. Karakostas 2009
10. Karpinski & Zelikovsky 1998
11. Dinur & Safra 2005
12. Khot, Minzer & Safra 2017; Dinur et al. 2018; Khot, Minzer & Safra 2018
13. Khot & Regev 2008
14. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Section 35.1: The vertex-cover problem". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 1024–1027. ISBN   0-262-03293-7.
15. Chakrabarti, Amit (Winter 2005). "Approximation Algorithms: Vertex Cover" (PDF). Computer Science 105. Dartmouth College . Retrieved 21 February 2005.
16. Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alexander C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (2020-07-13). "Automated design of thousands of nonrepetitive parts for engineering stable genetic systems". Nature Biotechnology. 38 (12): 1466–1475. doi:10.1038/s41587-020-0584-2. ISSN   1087-0156. PMID   32661437. S2CID   220506228.
17. Reis, Alexander C.; Halper, Sean M.; Vezeau, Grace E.; Cetnar, Daniel P.; Hossain, Ayaan; Clauer, Phillip R.; Salis, Howard M. (November 2019). "Simultaneous repression of multiple bacterial genes using nonrepetitive extra-long sgRNA arrays". Nature Biotechnology. 37 (11): 1294–1301. doi:10.1038/s41587-019-0286-9. ISSN   1546-1696. OSTI   1569832. PMID   31591552. S2CID   203852115.

References

• Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). "Improved Parameterized Upper Bounds for Vertex Cover". Mathematical Foundations of Computer Science 2006: 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings (PDF). Lecture Notes in Computer Science. Vol. 4162. Springer-Verlag. pp. 238–249. doi:10.1007/11821069_21. ISBN   978-3-540-37791-7.
• 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.
• Demaine, Erik; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2005). "Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs". Journal of the ACM . 52 (6): 866–893. doi:10.1145/1101821.1101823. S2CID   6238832 . Retrieved 2010-03-05.
• Dinur, Irit; Khot, Subhash; Kindler, Guy; Minzer, Dor; Safra, Muli (2018). "Towards a proof of the 2-to-1 games conjecture?". In Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.). Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018. Association for Computing Machinery. pp. 376–389. doi:10.1145/3188745.3188804. ISBN   978-1-4503-5559-9. ECCC   TR16-198.
• Dinur, Irit; Safra, Samuel (2005). "On the hardness of approximating minimum vertex cover". Annals of Mathematics . 162 (1): 439–485. CiteSeerX   10.1.1.125.334 . doi:10.4007/annals.2005.162.439.
• Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. doi:10.1007/3-540-29953-X. ISBN   978-3-540-29952-3 . Retrieved 2010-03-05.
• Garey, Michael R.; Johnson, David S. (1977). "The rectilinear Steiner tree problem is NP-complete". SIAM Journal on Applied Mathematics. 32 (4): 826–834. doi:10.1137/0132071.
• Garey, Michael R.; Johnson, David S. (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.
• Garey, Michael R.; Johnson, David S.; Stockmeyer, Larry (1974). "Some simplified NP-complete problems". Proceedings of the Sixth Annual ACM Symposium on Theory of Computing. pp. 47–63. doi:10.1145/800119.803884.
• Gallai, Tibor (1959). "Über extreme Punkt- und Kantenmengen". Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 2: 133–138.
• Karakostas, George (November 2009). "A better approximation ratio for the vertex cover problem" (PDF). ACM Transactions on Algorithms . 5 (4): 41:1–41:8. CiteSeerX   10.1.1.649.7407 . doi:10.1145/1597036.1597045. S2CID   2525818. ECCC   TR04-084.
• Karpinski, Marek; Zelikovsky, Alexander (1998). "Approximating dense cases of covering problems". Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Vol. 40. American Mathematical Society. pp. 169–178.
• Khot, Subhash; Minzer, Dor; Safra, Muli (2017). "On independent sets, 2-to-2 games, and Grassmann graphs". In Hatami, Hamed; McKenzie, Pierre; King, Valerie (eds.). Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. Association for Computing Machinery. pp. 576–589. doi:10.1145/3055399.3055432. ISBN   978-1-4503-4528-6. ECCC   TR16-124.
• Khot, Subhash; Minzer, Dor; Safra, Muli (2018). "Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion". 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). pp. 592–601. doi:10.1109/FOCS.2018.00062. ISBN   978-1-5386-4230-6. S2CID   3688775.
• Khot, Subhash; Regev, Oded (2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences . 74 (3): 335–349. doi: 10.1016/j.jcss.2007.06.019 .
• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998). Combinatorial Optimization: Algorithms and Complexity. Dover.
• Vazirani, Vijay V. (2003). Approximation Algorithms. Springer-Verlag. ISBN   978-3-662-04565-7.

External links

• Weisstein, Eric W. "Vertex Cover". MathWorld .
• Weisstein, Eric W. "Minimum Vertex Cover". MathWorld .
• Weisstein, Eric W. "Vertex Cover Number". MathWorld .
• River Crossings (and Alcuin Numbers) – Numberphile