Minimum Vertex Cover

A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph. The size of a minimum vertex cover of a graph  is known as the vertex cover number and is denoted .

Every minimum vertex cover is a minimal vertex cover (i.e., a vertex cover that is not a proper subset of any other cover), but not necessarily vice versa.

Finding a minimum vertex cover of a general graph is an NP-complete problem. However, for a bipartite graph, the König-Egeváry theorem allows a minimum vertex cover to be found in polynomial time.

A minimum vertex cover of a graph can be computed in the Wolfram Language using FindVertexCover[g]. There is currently no Wolfram Language function to compute all minimum vertex covers.

Minimum vertex covers correspond to the complements of maximum independent vertex sets.

REFERENCES

Pemmaraju, S. and Skiena, S. "Minimum Vertex Cover." §7.5.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 317, 2003.

Skiena, S. "Minimum Vertex Cover." §5.6.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 218, 1990.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.