Module org.jgrapht.core
Package org.jgrapht.alg.cycle

Class BergeGraphInspector<V,E>

java.lang.Object
org.jgrapht.alg.cycle.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 Details

    • BergeGraphInspector

      public BergeGraphInspector()

  • Method Details

    • 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