 java.lang.Object

 org.jgrapht.alg.cycle.BergeGraphInspector<V,E>

 Type Parameters:
V
 the graph vertex typeE
 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>)
orChordalityInspector
.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
Constructors Constructor Description BergeGraphInspector()

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description GraphPath<V,E>
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
.boolean
isBerge(Graph<V,E> g)
Performs the Berge Recognition Algorithm.boolean
isBerge(Graph<V,E> g, boolean computeCertificate)
Performs the Berge Recognition Algorithm.



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 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
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 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
public GraphPath<V,E> 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.

