FindVertexCover

FindVertexCover[g]
finds a vertex cover of the graph g with a minimum number of vertices.

FindVertexCover[{vw,}]
uses rules vw to specify the graph g.

DetailsDetails

  • FindVertexCover returns a list of vertices.
  • FindVertexCover will return an empty list if no vertex cover is found.
  • A vertex cover is a set of vertices that is incident to every edge.
  • FindVertexCover works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.

Background & Context
Background & Context

  • FindVertexCover finds a single vertex cover of a graph, where a vertex cover is a subset of vertices satisfying the condition that each edge is incident to some vertex.
  • FindVertexCover[g] finds a minimum vertex cover (i.e. a vertex cover of smallest possible size) of a graph g, while FindVertexCover[g,k] finds a vertex cover of size k. The size of a minimum vertex cover of a graph g is known as its vertex cover number. The problem of finding a minimum vertex cover (and hence the vertex cover number) of a general graph is NP-complete, meaning computation can be exponentially slow. However, a minimum vertex cover can be found in polynomial time for bipartite graphs (i.e. graphs whose vertex set can be partitioned into two independent sets).
  • Vertex covers are closely related to independent vertex sets (which are sets of vertices such that no two belong to the same edge). In particular, a set of vertices is a vertex cover if and only if its complement forms an independent vertex set. The counts of vertex covers and independent vertex sets in a graph are therefore the same. Furthermore, the sum of the independence number (size of a maximum independent vertex) and the vertex cover number (size of a minimum vertex cover) of an undirected graph equals the vertex count.
  • A vertex cover of a graph can be formed by taking the endpoints from each edge in a maximal independent edge set. (Here, an independent edge set is a set of edges such that no two member edges share a vertex. A maximal independent edge set is an independent edge set to which no other edge of the graph can be added without violating independence, while a maximum independent edge set is an independent edge set of maximum possible size for a given graph.) As a result, the size of a minimum vertex cover is always at most as large as twice the size of a maximum independent edge set. The KönigEgerváry theorem states that for bipartite graphs, the size of a maximum independent edge set (i.e. the matching number) equals its vertex cover number.
  • VertexCoverQ can be used to test if a given vertex set forms a vertex cover of a specified graph. A trivial implementation to find multiple vertex covers can therefore be written by applying VertexCoverQ to any desired subsets of a graph's vertices. Similarly, FindIndependentVertexSet can be used to find one or more maximal independent vertex sets in a graph, each of whose complements is a vertex cover. FindEdgeCover performs the analogous test to FindVertexCover for edge covers of a graph.
Introduced in 2010
(8.0)
| Updated in 2015
(10.3)