Package com.jgalgo.alg.cover

Interface VertexCover

All Known Implementing Classes:

VertexCoverAbstract, VertexCoverBarYehuda

public interface VertexCover

Minimum weighted vertex cover algorithm.

Given a graph \(G=(V,E)\) a vertex cover is a set \(S \subseteq V\) for which for any edge \((u,v) \in E\) at least one of \(u\) or \(v\) are in \(S\). Given a vertex weight function \(w:V \rightarrow R\), the weight of a vertex cover is the weight sum of the vertices in the cover. The minimum vertex cover is the vertex cover with the minimum weight.

Note that finding the actual minimum vertex cover is an NP-hard problem, even for a weight function that assign \(1\) to each vertex. Therefore, algorithms implementing this interface provide an approximation for the actual optimal solution.

Use newInstance() to get a default implementation of this interface.

Author:

Barak Ugav

See Also:

EdgeCover, Wikipedia

Method Summary

Modifier and Type	Method	Description
<V,E> Set<V>	computeMinimumVertexCover(Graph<V,E> g, WeightFunction<V> w)	Compute a minimum vertex cover of a graph with respect to a vertex weight function.
static <V,E> boolean	isCover(Graph<V,E> g, Collection<V> vertices)	Check whether a set of vertices is a vertex cover of a graph.
static VertexCover	newInstance()	Create a new vertex cover algorithm object.

Method Detail

computeMinimumVertexCover

<V,E> Set<V> computeMinimumVertexCover(Graph<V,E> g,
                                             WeightFunction<V> w)

Compute a minimum vertex cover of a graph with respect to a vertex weight function.

Note that finding the minimum vertex cover is an NP-hard problem, therefore the result of this function is an approximation of the optimal solution.

If g is IntGraph, the returned object is IntSet. If g is IntGraph, prefer to pass IWeightFunction as w to avoid boxing/unboxing.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - a vertex weight function

Returns:

a minimum vertex cover

isCover

static <V,E> boolean isCover(Graph<V,E> g,
                                   Collection<V> vertices)

Check whether a set of vertices is a vertex cover of a graph.

A set of vertices is a vertex cover of a graph if for every edge in the graph at least one of its vertices is in the set. In addition, the collection of the vertices must not contain duplicates.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

vertices - a collection of vertices that should cover all the edges in the graph

Returns:

true if vertices is a vertex cover of g

newInstance

static VertexCover newInstance()

Create a new vertex cover algorithm object.

This is the recommended way to instantiate a new VertexCover object.

Returns:

a default implementation of VertexCover