# 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 NP-Complete 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 2-opt algorithm for a minimum weighted vertex cover by R. Bar-Yehuda and S. Even.

This is a 2-approximation algorithm with running time $$\mathcal{O}(m)$$.

Parameters
• graph – the input graph. It must be undirected. Self-loops 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 2-opt algorithm of Clarkson.

The algorithm runs in time $$\mathcal{O}(m \log n)$$ and is a 2-approximation which means that the solution is guaranteed to be at most twice the optimum.

Clarkson, Kenneth L. A modification of the greedy algorithm for vertex cover. Information Processing Letters 16.1 (1983): 23-25.

Parameters
• graph – the input graph. It must be undirected. Self-loops 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 2-opt algorithm for the minimum vertex cover.

This is a 2-approximation algorithm with running time $$\mathcal{O}(m)$$.

Parameters

graph – the input graph. It must be undirected. Self-loops 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 150-200 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. Self-loops and multiple edges are allowed

• vertex_weights – an optional dictionary of vertex weights

Returns

a tuple (weight, vertex set)