# FindVertexCover

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

## Basic Examples(1)

Find a vertex cover:

 In:= In:= Out= Show the cover:

 In:= Out= ## Properties & Relations(6)

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