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)

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)

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.

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): 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)

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)

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)

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)