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.

Details

  • 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

  • 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.

Examples

open allclose all

Basic Examples  (1)

Find a vertex cover:

Show the cover:

Scope  (7)

FindVertexCover works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Mixed graphs:

Use rules to specify the graph:

FindVertexCover works with large graphs:

Properties & Relations  (6)

The result of FindVertexCover can be tested by VertexCoverQ:

A set of vertices is a vertex cover if its complement is an independent set:

Check that the complement set of vertices is independent:

The total size of the vertex cover and the largest independent set equals the vertex count:

The complement of the vertex cover in GraphComplement is a clique in its original graph:

Compute the complement using the same embedding:

Its complement is a clique:

The complete bipartite graph has vertex cover of size :

The largest independent edge set in a bipartite graph has the same size as the smallest vertex cover:

Introduced in 2010
 (8.0)
 |
Updated in 2014
 (10.0)
2015
 (10.3)