Package org.jgrapht.alg.cycle

Class BergeGraphInspector<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    public class BergeGraphInspector<V,​E>
extends 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.

    Author:
    Philipp S. Kaesgen (pkaesgen@freenet.de)

    • Constructor Detail

      • BergeGraphInspector

        public BergeGraphInspector()

    • Method Detail

      • 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