Vertex Cover¶
Algorithms¶
A vertex cover is a set of vertices which covers (touches) all edges of the graph. Finding a minimum vertex cover is an NPComplete problem. This module contains various algorithms for the computation of “good” vertex covers. For more information, see Vertex Cover.

jgrapht.algorithms.vertexcover.
baryehuda_even
(graph, vertex_weights=None)[source]¶ The 2opt algorithm for a minimum weighted vertex cover by R. BarYehuda and S. Even.
This is a 2approximation algorithm with running time \(\mathcal{O}(m)\).
 Parameters
graph – the input graph. It must be undirected. Selfloops and multiple edges are allowed
vertex_weights – an optional dictionary of vertex weights
 Returns
a tuple (weight, vertex set)

jgrapht.algorithms.vertexcover.
clarkson
(graph, vertex_weights=None)[source]¶ Compute a vertex cover using the 2opt algorithm of Clarkson.
The algorithm runs in time \(\mathcal{O}(m \log n)\) and is a 2approximation which means that the solution is guaranteed to be at most twice the optimum.
For more information see the following paper:
Clarkson, Kenneth L. A modification of the greedy algorithm for vertex cover. Information Processing Letters 16.1 (1983): 2325.
 Parameters
graph – the input graph. It must be undirected. Selfloops and multiple edges are allowed
vertex_weights – an optional dictionary of vertex weights
 Returns
a tuple (weight, vertex set)

jgrapht.algorithms.vertexcover.
edgebased
(graph)[source]¶ A 2opt algorithm for the minimum vertex cover.
This is a 2approximation algorithm with running time \(\mathcal{O}(m)\).
 Parameters
graph – the input graph. It must be undirected. Selfloops and multiple edges are allowed
 Returns
a tuple (weight, vertex set)

jgrapht.algorithms.vertexcover.
exact
(graph, vertex_weights=None)[source]¶ Compute a vertex cover exactly using a recursive algorithm.
At each recursive step the algorithm picks a vertex and either includes in the cover or it includes all of its neighbors. To speed up the algorithm, memoization and a bounding procedure is also used.
Can solve instances with around 150200 vertices to optimality.
 Parameters
graph – the input graph. It must be undirected
vertex_weights – an optional dictionary of vertex weights
 Returns
a tuple (weight, vertex set)

jgrapht.algorithms.vertexcover.
greedy
(graph, vertex_weights=None)[source]¶ A greedy algorithm for the vertex cover problem.
At each iteration the algorithm picks the vertex \(v\) with the minimum ration of weight over degree. Afterwards it removes all its incident edges and recurses.
Its running time is \(\mathcal{O}(m \log n)\). The implementation supports both the uniform and the weighted case where the graph vertices have weights.
 Parameters
graph – the input graph. It must be undirected. Selfloops and multiple edges are allowed
vertex_weights – an optional dictionary of vertex weights
 Returns
a tuple (weight, vertex set)