 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
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): 143186, 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 NPhard.
 Author:
 Philipp S. Kaesgen (pkaesgen@freenet.de)

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionReturns the certificate in the form of a hole or antihole in the inspected graph, when theisBerge(org.jgrapht.Graph<V, E>, boolean)
method is previously called withcomputeCertificate=true
.boolean
Performs the Berge Recognition Algorithm.boolean
Performs the Berge Recognition Algorithm.

Constructor Details

BergeGraphInspector
public BergeGraphInspector()


Method Details

isBerge
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 nearcleaner subsets of $V(G)$ are determined. For each of them in turn it is checked, if this subset is a nearcleaner 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 nearcleaners 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, ifcomputeCertificate
istrue
.Running this method takes $O(V^9)$, and computing the certificate takes $O(V^5)$.
 Parameters:
g
 A graphcomputeCertificate
 toggles certificate computation Returns:
 whether g is Berge and, thus, perfect

isBerge
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 nearcleaner subsets of $V(G)$ are determined. For each of them in turn it is checked, if this subset is a nearcleaner 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 nearcleaners 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)
withcomputeCertificate=true
.Running this method takes $O(V^9)$.
 Parameters:
g
 A graph Returns:
 whether g is Berge and, thus, perfect

getCertificate
Returns the certificate in the form of a hole or antihole in the inspected graph, when theisBerge(org.jgrapht.Graph<V, E>, boolean)
method is previously called withcomputeCertificate=true
. Returns null if the inspected graph is perfect.
