Package com.jgalgo.alg

Interface VertexCover

  • 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. A builder obtained via newBuilder() may support different options to obtain different implementations.

    Author:
    Barak Ugav
    See Also:
    EdgeCover, Wikipedia

    • 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. The VertexCover.Builder might support different options to obtain different implementations.

        Returns:
        a default implementation of VertexCover