V
 the graph vertex typeE
 the graph edge typepublic 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): 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.
Constructor and Description 

BergeGraphInspector() 
Modifier and Type  Method and Description 

GraphPath<V,E> 
getCertificate()
Returns the certificate in the form of a hole or antihole in the inspected graph, when the
isBerge(org.jgrapht.Graph<V, E>, boolean) method is previously called with
computeCertificate=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.

public boolean isBerge(Graph<V,E> g, boolean computeCertificate)
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,
if computeCertificate
is true
.
Running this method takes $O(V^9)$, and computing the certificate takes $O(V^5)$.
g
 A graphcomputeCertificate
 toggles certificate computationpublic boolean isBerge(Graph<V,E> g)
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)
with computeCertificate=true
.
Running this method takes $O(V^9)$.
g
 A graphpublic GraphPath<V,E> getCertificate()
isBerge(org.jgrapht.Graph<V, E>, boolean)
method is previously called with
computeCertificate=true
. Returns null if the inspected graph is perfect.Copyright © 2019. All rights reserved.