Class BergeGraphInspector<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class BergeGraphInspector<V,​E>
    extends java.lang.Object

    Tests whether a graph is perfect. A perfect graph, also known as a Berge graph, is a graph $G$ such that for every induced subgraph of $G$, the clique number $\chi(G)$ equals the chromatic number $\omega(G)$, i.e., $\omega(G)=\chi(G)$. Another characterization of perfect graphs is given by the Strong Perfect Graph Theorem [M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas. The strong perfect graph theorem Annals of Mathematics, vol 164(1): pp. 51–230, 2006]: A graph $G$ is perfect if neither $G$ nor its complement $\overline{G}$ have an odd hole. A hole in $G$ is an induced subgraph of $G$ that is a cycle of length at least four, and it is odd or even if it has odd (or even, respectively) length.

    Some special classes of graphs are are known to be perfect, e.g. Bipartite graphs and Chordal graphs. Testing whether a graph is resp. Bipartite or Chordal can be done efficiently using GraphTests.isBipartite(org.jgrapht.Graph<V, E>) or ChordalityInspector.

    The implementation of this class is based on the paper: M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, and K. Vuskovic. Recognizing Berge Graphs. Combinatorica 25(2): 143--186, 2003.

    Special Thanks to Maria Chudnovsky for her kind help.

    The runtime complexity of this implementation is $O(|V|^9|)$. This implementation is far more efficient than simplistically testing whether graph $G$ or its complement $\overline{G}$ have an odd cycle, because testing whether one graph can be found as an induced subgraph of another is known to be NP-hard.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void bfOddHoleCertificate​(Graph<V,​E> g)  
      (package private) boolean containsCleanShortestOddHole​(Graph<V,​E> g)
      Checks whether a graph contains a clean shortest odd hole.
      (package private) boolean containsJewel​(Graph<V,​E> g)
      Checks whether a graph contains a Jewel.
      (package private) boolean containsPyramid​(Graph<V,​E> g)
      Checks whether a graph contains a pyramid.
      private boolean containsShortestOddHole​(Graph<V,​E> g, java.util.Set<V> x)
      Checks whether the vertex set of a graph without a vertex set X contains a shortest odd hole.
      private java.util.List<java.util.Set<V>> findAllAnticomponentsOfY​(Graph<V,​E> g, java.util.Set<V> y)
      Returns all anticomponents of a graph and a vertex set.
      private java.util.List<java.util.Set<V>> findAllComponents​(Graph<V,​E> g, java.util.Set<V> f)
      Finds all Components of a set F contained in V(g)
      private java.util.Set<V> findMaximalConnectedSubset​(Graph<V,​E> g, java.util.Set<V> setX, V v1, V v2, V v5)
      For each anticomponent X, find the maximal connected subset F' containing v5 with the properties that v1,v2 have no neighbours in F' and no vertex of F'\v5 is X-complete
      GraphPath<V,​E> getCertificate()
      Returns the certificate in the form of a hole or anti-hole in the inspected graph, when the isBerge(org.jgrapht.Graph<V, E>, boolean) method is previously called with computeCertificate=true.
      private GraphPath<V,​E> getPathAvoidingX​(Graph<V,​E> g, V start, V end, java.util.Set<V> x)
      Returns a path in g from start to end avoiding the vertices in X
      private boolean hasANeighbour​(Graph<V,​E> g, java.util.Set<V> set, V v)
      Reports whether v has at least one neighbour in set
      private boolean hasANonneighbourInX​(Graph<V,​E> g, V v, java.util.Set<V> setX)
      Reports whether a vertex has at least one nonneighbour in X
      private boolean hasConfigurationType1​(Graph<V,​E> g)
      Checks whether a graph has a configuration of type T1.
      (package private) boolean hasConfigurationType2​(Graph<V,​E> g)
      Checks whether a graph is of configuration type T2.
      (package private) boolean hasConfigurationType3​(Graph<V,​E> g)
      Checks whether a graph is of configuration type T3.
      private java.util.List<V> intersectGraphPaths​(GraphPath<V,​E> p1, GraphPath<V,​E> p2)
      Lists the vertices which are covered by two paths
      boolean isBerge​(Graph<V,​E> g)
      Performs the Berge Recognition Algorithm.
      boolean isBerge​(Graph<V,​E> g, boolean computeCertificate)
      Performs the Berge Recognition Algorithm.
      private boolean isTripleRelevant​(Graph<V,​E> g, V a, V b, V c)
      A triple (a,b,c) of vertices is relevant if a,b are distinct and nonadjacent, and c is not contained in N(a,b) (possibly c is contained in {a,b}).
      (package private) boolean isYXComplete​(Graph<V,​E> g, V y, java.util.Set<V> x)
      A vertex y is X-complete if y contained in V(g)\X is adjacent to every vertex in X.
      private java.util.Set<V> n​(Graph<V,​E> g, V a, V b)
      N(a,b) is the set of all {a,b}-complete vertices
      private GraphPath<V,​E> p​(Graph<V,​E> g, GraphPath<V,​E> pathS, GraphPath<V,​E> pathT, V m, V b1, V b2, V b3, V s1, V s2, V s3)
      Assembles a GraphPath of the Paths S and T.
      private int r​(Graph<V,​E> g, java.util.Set<V> nAB, V c)
      r(a,b,c) is the cardinality of the largest anticomponent of N(a,b) that contains a nonneighbour of c (or 0, if c is N(a,b)-complete)
      private boolean routine1​(Graph<V,​E> g, java.util.Set<V> x)
      Checks whether a clean shortest odd hole is in g or whether X is a cleaner for an amenable shortest odd hole
      private boolean routine2​(Graph<V,​E> g)
      If true, the graph is not Berge.
      (package private) java.util.Set<java.util.Set<V>> routine3​(Graph<V,​E> g)
      Returns a set of vertex sets that may be near-cleaners for an amenable hole in g.
      private java.util.Set<V> w​(Graph<V,​E> g, java.util.Set<V> nAB, V c)
      W(a,b,c) is the anticomponent of N(a,b)+{c} that contains c
      private java.util.Set<V> x​(Graph<V,​E> g, java.util.Set<V> nAB, V c)
      X(a,b,c)=Y(a,b,c)+Z(a,b,c)
      private java.util.Set<V> y​(Graph<V,​E> g, java.util.Set<V> nAB, V c)
      Y(a,b,c) is the union of all anticomponents of N(a,b) that have cardinality strictly greater than r(a,b,c)
      private java.util.Set<V> z​(Graph<V,​E> g, java.util.Set<V> nAB, V c)
      Z(a,b,c) is the set of all (Y(a,b,c)+W(a,b,c))-complete vertices
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • certify

        private boolean certify
    • Constructor Detail

      • BergeGraphInspector

        public BergeGraphInspector()
    • Method Detail

      • intersectGraphPaths

        private java.util.List<V> intersectGraphPaths​(GraphPath<V,​E> p1,
                                                      GraphPath<V,​E> p2)
        Lists the vertices which are covered by two paths
        Parameters:
        p1 - A Path in g
        p2 - A Path in g
        Returns:
        Set of vertices covered by both p1 and p2
      • p

        private GraphPath<V,​E> p​(Graph<V,​E> g,
                                       GraphPath<V,​E> pathS,
                                       GraphPath<V,​E> pathT,
                                       V m,
                                       V b1,
                                       V b2,
                                       V b3,
                                       V s1,
                                       V s2,
                                       V s3)
        Assembles a GraphPath of the Paths S and T. Required for the Pyramid Checker
        Parameters:
        g - A Graph
        pathS - A Path in g
        pathT - A Path in g
        m - A vertex
        b1 - A base vertex
        b2 - A base vertex
        b3 - A base vertex
        s1 - A vertex
        s2 - A vertex
        s3 - A vertex
        Returns:
        The conjunct path of S and T
      • bfOddHoleCertificate

        private void bfOddHoleCertificate​(Graph<V,​E> g)
      • containsPyramid

        boolean containsPyramid​(Graph<V,​E> g)
        Checks whether a graph contains a pyramid. Running time: O(|V(g)|^9)
        Parameters:
        g - Graph
        Returns:
        Either it finds a pyramid (and hence an odd hole) in g, or it determines that g contains no pyramid
      • findAllComponents

        private java.util.List<java.util.Set<V>> findAllComponents​(Graph<V,​E> g,
                                                                   java.util.Set<V> f)
        Finds all Components of a set F contained in V(g)
        Parameters:
        g - A graph
        f - A vertex subset of g
        Returns:
        Components of F in g
      • containsJewel

        boolean containsJewel​(Graph<V,​E> g)
        Checks whether a graph contains a Jewel. Running time: O(|V(g)|^6)
        Parameters:
        g - Graph
        Returns:
        Decides whether there is a jewel in g
      • containsCleanShortestOddHole

        boolean containsCleanShortestOddHole​(Graph<V,​E> g)
        Checks whether a graph contains a clean shortest odd hole. Running time: O(|V(g)|^4)
        Parameters:
        g - Graph containing no pyramid or jewel
        Returns:
        Decides whether g contains a clean shortest odd hole
      • getPathAvoidingX

        private GraphPath<V,​E> getPathAvoidingX​(Graph<V,​E> g,
                                                      V start,
                                                      V end,
                                                      java.util.Set<V> x)
        Returns a path in g from start to end avoiding the vertices in X
        Parameters:
        g - A Graph
        start - start vertex
        end - end vertex
        x - set of vertices which should not be in the graph
        Returns:
        A Path in G\X
      • containsShortestOddHole

        private boolean containsShortestOddHole​(Graph<V,​E> g,
                                                java.util.Set<V> x)
        Checks whether the vertex set of a graph without a vertex set X contains a shortest odd hole. Running time: O(|V(g)|^4)
        Parameters:
        g - Graph containing neither pyramid nor jewel
        x - Subset of V(g) and a possible Cleaner for an odd hole
        Returns:
        Determines whether g has an odd hole such that X is a near-cleaner for it
      • routine1

        private boolean routine1​(Graph<V,​E> g,
                                 java.util.Set<V> x)
        Checks whether a clean shortest odd hole is in g or whether X is a cleaner for an amenable shortest odd hole
        Parameters:
        g - A graph, containing no pyramid or jewel
        x - A subset X of V(g) and a possible Cleaner for an odd hole
        Returns:
        Returns whether g has an odd hole or there is no shortest odd hole in C such that X is a near-cleaner for C.
      • hasConfigurationType1

        private boolean hasConfigurationType1​(Graph<V,​E> g)
        Checks whether a graph has a configuration of type T1. A configuration of type T1 in g is a hole of length 5
        Parameters:
        g - A Graph
        Returns:
        whether g contains a configuration of Type T1 (5-cycle)
      • isYXComplete

        boolean isYXComplete​(Graph<V,​E> g,
                             V y,
                             java.util.Set<V> x)
        A vertex y is X-complete if y contained in V(g)\X is adjacent to every vertex in X.
        Parameters:
        g - A Graph
        y - Vertex whose X-completeness is to assess
        x - Set of vertices
        Returns:
        whether y is X-complete
      • findAllAnticomponentsOfY

        private java.util.List<java.util.Set<V>> findAllAnticomponentsOfY​(Graph<V,​E> g,
                                                                          java.util.Set<V> y)
        Returns all anticomponents of a graph and a vertex set.
        Parameters:
        g - A Graph
        y - A set of vertices
        Returns:
        List of anticomponents of Y in g
      • hasConfigurationType2

        boolean hasConfigurationType2​(Graph<V,​E> g)

        Checks whether a graph is of configuration type T2. A configuration of type T2 in g is a sequence v1,v2,v3,v4,P,X such that:

        • v1-v2-v3-v4 is a path of g
        • X is an anticomponent of the set of all {v1,v2,v4}-complete vertices
        • P is a path in G\(X+{v2,v3}) between v1,v4, and no vertex in P*, i.e. P's interior, is X-complete or adjacent to v2 or adjacent to v3
        An example is the complement graph of a cycle-7-graph
        Parameters:
        g - A Graph
        Returns:
        whether g contains a configuration of Type T2
      • hasANeighbour

        private boolean hasANeighbour​(Graph<V,​E> g,
                                      java.util.Set<V> set,
                                      V v)
        Reports whether v has at least one neighbour in set
        Parameters:
        g - A Graph
        set - A set of vertices
        v - A vertex
        Returns:
        whether v has at least one neighbour in set
      • findMaximalConnectedSubset

        private java.util.Set<V> findMaximalConnectedSubset​(Graph<V,​E> g,
                                                            java.util.Set<V> setX,
                                                            V v1,
                                                            V v2,
                                                            V v5)
        For each anticomponent X, find the maximal connected subset F' containing v5 with the properties that v1,v2 have no neighbours in F' and no vertex of F'\v5 is X-complete
        Parameters:
        g - A Graph
        setX - A set of vertices
        v1 - A vertex
        v2 - A vertex
        v5 - A Vertex
        Returns:
        The maximal connected vertex subset containing v5, no neighbours of v1 and v2, and no X-complete vertex except v5
      • hasANonneighbourInX

        private boolean hasANonneighbourInX​(Graph<V,​E> g,
                                            V v,
                                            java.util.Set<V> setX)
        Reports whether a vertex has at least one nonneighbour in X
        Parameters:
        g - A Graph
        v - A Vertex
        setX - A set of vertices
        Returns:
        whether v has a nonneighbour in X
      • hasConfigurationType3

        boolean hasConfigurationType3​(Graph<V,​E> g)

        Checks whether a graph is of configuration type T3. A configuration of type T3 in g is a sequence v1,...,v6,P,X such that

        • v1,...,v6 are distinct vertices of g
        • v1v2,v3v4,v2v3,v3v5,v4v6 are edges, and v1v3,v2v4,v1v5,v2v5,v1v6,v2v6,v4v5 are non-edges
        • X is an anticomponent of the set of all {v1,v2,v5}-complete vertices, and v3,v4 are not X-complete
        • P is a path of g\(X+{v1,v2,v3,v4}) between v5,v6, and no vertex in P* is X-complete or adjacent to v1 or adjacent to v2
        • if v5v6 is an edge then v6 is not X-complete
        Parameters:
        g - A Graph
        Returns:
        whether g contains a configuration of Type T3
      • routine2

        private boolean routine2​(Graph<V,​E> g)
        If true, the graph is not Berge. Checks whether g contains a Pyramid, Jewel, configuration type 1, 2 or 3.
        Parameters:
        g - A Graph
        Returns:
        whether g contains a pyramid, a jewel, a T1, a T2, or a T3
      • n

        private java.util.Set<V> n​(Graph<V,​E> g,
                                   V a,
                                   V b)
        N(a,b) is the set of all {a,b}-complete vertices
        Parameters:
        g - A Graph
        a - A Vertex
        b - A Vertex
        Returns:
        The set of all {a,b}-complete vertices
      • r

        private int r​(Graph<V,​E> g,
                      java.util.Set<V> nAB,
                      V c)
        r(a,b,c) is the cardinality of the largest anticomponent of N(a,b) that contains a nonneighbour of c (or 0, if c is N(a,b)-complete)
        Parameters:
        g - a Graph
        nAB - The set of all {a,b}-complete vertices
        c - A vertex
        Returns:
        The cardinality of the largest anticomponent of N(a,b) that contains a nonneighbour of c (or 0, if c is N(a,b)-complete)
      • y

        private java.util.Set<V> y​(Graph<V,​E> g,
                                   java.util.Set<V> nAB,
                                   V c)
        Y(a,b,c) is the union of all anticomponents of N(a,b) that have cardinality strictly greater than r(a,b,c)
        Parameters:
        g - A graph
        nAB - The set of all {a,b}-complete vertices
        c - A vertex
        Returns:
        A Set of vertices with cardinality greater r(a,b,c)
      • w

        private java.util.Set<V> w​(Graph<V,​E> g,
                                   java.util.Set<V> nAB,
                                   V c)
        W(a,b,c) is the anticomponent of N(a,b)+{c} that contains c
        Parameters:
        g - A graph
        nAB - The set of all {a,b}-complete vertices
        c - A vertex
        Returns:
        The anticomponent of N(a,b)+{c} containing c
      • z

        private java.util.Set<V> z​(Graph<V,​E> g,
                                   java.util.Set<V> nAB,
                                   V c)
        Z(a,b,c) is the set of all (Y(a,b,c)+W(a,b,c))-complete vertices
        Parameters:
        g - A graph
        nAB - The set of all {a,b}-complete vertices
        c - A vertex
        Returns:
        A set of vertices
      • x

        private java.util.Set<V> x​(Graph<V,​E> g,
                                   java.util.Set<V> nAB,
                                   V c)
        X(a,b,c)=Y(a,b,c)+Z(a,b,c)
        Parameters:
        g - A graph
        nAB - The set of all {a,b}-complete vertices
        c - A vertex
        Returns:
        The union of Y(a,b,c) and Z(a,b,c)
      • isTripleRelevant

        private boolean isTripleRelevant​(Graph<V,​E> g,
                                         V a,
                                         V b,
                                         V c)
        A triple (a,b,c) of vertices is relevant if a,b are distinct and nonadjacent, and c is not contained in N(a,b) (possibly c is contained in {a,b}).
        Parameters:
        g - A graph
        a - A vertex
        b - A vertex
        c - A vertex
        Returns:
        Assessement whether a,b,c is a relevant triple
      • routine3

        java.util.Set<java.util.Set<V>> routine3​(Graph<V,​E> g)
        Returns a set of vertex sets that may be near-cleaners for an amenable hole in g.
        Parameters:
        g - A graph
        Returns:
        possible near-cleaners
      • isBerge

        public boolean isBerge​(Graph<V,​E> g,
                               boolean computeCertificate)
        Performs the Berge Recognition Algorithm.

        First this algorithm is used to test whether $G$ or its complement contain a jewel, a pyramid or a configuration of type 1, 2 or 3. If so, it is output that $G$ is not Berge. If not, then every shortest odd hole in $G$ is amenable. This asserted, the near-cleaner subsets of $V(G)$ are determined. For each of them in turn it is checked, if this subset is a near-cleaner and, thus, if there is an odd hole. If an odd hole is found, this checker will output that $G$ is not Berge. If no odd hole is found, all near-cleaners for the complement graph are determined and it will be proceeded as before. If again no odd hole is detected, $G$ is Berge.

        A certificate can be obtained through the getCertificate() method, if computeCertificate is true.

        Running this method takes $O(|V|^9)$, and computing the certificate takes $O(|V|^5)$.

        Parameters:
        g - A graph
        computeCertificate - toggles certificate computation
        Returns:
        whether g is Berge and, thus, perfect
      • isBerge

        public boolean isBerge​(Graph<V,​E> g)
        Performs the Berge Recognition Algorithm.

        First this algorithm is used to test whether $G$ or its complement contain a jewel, a pyramid or a configuration of type 1, 2 or 3. If so, it is output that $G$ is not Berge. If not, then every shortest odd hole in $G$ is amenable. This asserted, the near-cleaner subsets of $V(G)$ are determined. For each of them in turn it is checked, if this subset is a near-cleaner and, thus, if there is an odd hole. If an odd hole is found, this checker will output that $G$ is not Berge. If no odd hole is found, all near-cleaners for the complement graph are determined and it will be proceeded as before. If again no odd hole is detected, $G$ is Berge.

        This method by default does not compute a certificate. For obtaining a certificate, call isBerge(org.jgrapht.Graph<V, E>, boolean) with computeCertificate=true.

        Running this method takes $O(|V|^9)$.

        Parameters:
        g - A graph
        Returns:
        whether g is Berge and, thus, perfect
      • getCertificate

        public GraphPath<V,​E> getCertificate()
        Returns the certificate in the form of a hole or anti-hole in the inspected graph, when the isBerge(org.jgrapht.Graph<V, E>, boolean) method is previously called with computeCertificate=true. Returns null if the inspected graph is perfect.
        Returns:
        a hole or anti-hole in the inspected graph, null if the graph is perfect