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:

  • 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 Details

    • 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