- 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): 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.
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate void
bfOddHoleCertificate
(Graph<V, E> g) (package private) boolean
Checks whether a graph contains a clean shortest odd hole.(package private) boolean
containsJewel
(Graph<V, E> g) Checks whether a graph contains a Jewel.(package private) boolean
containsPyramid
(Graph<V, E> g) Checks whether a graph contains a pyramid.private boolean
Checks whether the vertex set of a graph without a vertex set X contains a shortest odd hole.Returns all anticomponents of a graph and a vertex set.Finds all Components of a set F contained in V(g)For each anticomponent X, find the maximal connected subset F' containing v5 with the properties that v1,v2 have no neighbours in F' and no vertex of F'\v5 is X-completeReturns the certificate in the form of a hole or anti-hole in the inspected graph, when theisBerge(org.jgrapht.Graph<V, E>, boolean)
method is previously called withcomputeCertificate=true
.Returns a path in g from start to end avoiding the vertices in Xprivate boolean
Reports whether v has at least one neighbour in setprivate boolean
Reports whether a vertex has at least one nonneighbour in Xprivate boolean
hasConfigurationType1
(Graph<V, E> g) Checks whether a graph has a configuration of type T1.(package private) boolean
hasConfigurationType2
(Graph<V, E> g) Checks whether a graph is of configuration type T2.(package private) boolean
hasConfigurationType3
(Graph<V, E> g) Checks whether a graph is of configuration type T3.Lists the vertices which are covered by two pathsboolean
Performs the Berge Recognition Algorithm.boolean
Performs the Berge Recognition Algorithm.private boolean
A triple (a,b,c) of vertices is relevant if a,b are distinct and nonadjacent, and c is not contained in N(a,b) (possibly c is contained in {a,b}).(package private) boolean
A vertex y is X-complete if y contained in V(g)\X is adjacent to every vertex in X.N(a,b) is the set of all {a,b}-complete verticesp
(Graph<V, E> g, GraphPath<V, E> pathS, GraphPath<V, E> pathT, V m, V b1, V b2, V b3, V s1, V s2, V s3) Assembles a GraphPath of the Paths S and T.private int
r(a,b,c) is the cardinality of the largest anticomponent of N(a,b) that contains a nonneighbour of c (or 0, if c is N(a,b)-complete)private boolean
Checks whether a clean shortest odd hole is in g or whether X is a cleaner for an amenable shortest odd holeprivate boolean
If true, the graph is not Berge.Returns a set of vertex sets that may be near-cleaners for an amenable hole in g.W(a,b,c) is the anticomponent of N(a,b)+{c} that contains cX(a,b,c)=Y(a,b,c)+Z(a,b,c)Y(a,b,c) is the union of all anticomponents of N(a,b) that have cardinality strictly greater than r(a,b,c)Z(a,b,c) is the set of all (Y(a,b,c)+W(a,b,c))-complete vertices
-
Field Details
-
certificate
-
certify
private boolean certify
-
-
Constructor Details
-
BergeGraphInspector
public BergeGraphInspector()
-
-
Method Details
-
intersectGraphPaths
Lists the vertices which are covered by two paths- Parameters:
p1
- A Path in gp2
- A Path in g- Returns:
- Set of vertices covered by both p1 and p2
-
p
private GraphPath<V,E> p(Graph<V, E> g, GraphPath<V, E> pathS, GraphPath<V, E> pathT, V m, V b1, V b2, V b3, V s1, V s2, V s3) Assembles a GraphPath of the Paths S and T. Required for the Pyramid Checker- Parameters:
g
- A GraphpathS
- A Path in gpathT
- A Path in gm
- A vertexb1
- A base vertexb2
- A base vertexb3
- A base vertexs1
- A vertexs2
- A vertexs3
- A vertex- Returns:
- The conjunct path of S and T
-
bfOddHoleCertificate
-
containsPyramid
Checks whether a graph contains a pyramid. Running time: O(|V(g)|^9)- Parameters:
g
- Graph- Returns:
- Either it finds a pyramid (and hence an odd hole) in g, or it determines that g contains no pyramid
-
findAllComponents
Finds all Components of a set F contained in V(g)- Parameters:
g
- A graphf
- A vertex subset of g- Returns:
- Components of F in g
-
containsJewel
Checks whether a graph contains a Jewel. Running time: O(|V(g)|^6)- Parameters:
g
- Graph- Returns:
- Decides whether there is a jewel in g
-
containsCleanShortestOddHole
Checks whether a graph contains a clean shortest odd hole. Running time: O(|V(g)|^4)- Parameters:
g
- Graph containing no pyramid or jewel- Returns:
- Decides whether g contains a clean shortest odd hole
-
getPathAvoidingX
Returns a path in g from start to end avoiding the vertices in X- Parameters:
g
- A Graphstart
- start vertexend
- end vertexx
- set of vertices which should not be in the graph- Returns:
- A Path in G\X
-
containsShortestOddHole
Checks whether the vertex set of a graph without a vertex set X contains a shortest odd hole. Running time: O(|V(g)|^4)- Parameters:
g
- Graph containing neither pyramid nor jewelx
- Subset of V(g) and a possible Cleaner for an odd hole- Returns:
- Determines whether g has an odd hole such that X is a near-cleaner for it
-
routine1
Checks whether a clean shortest odd hole is in g or whether X is a cleaner for an amenable shortest odd hole- Parameters:
g
- A graph, containing no pyramid or jewelx
- A subset X of V(g) and a possible Cleaner for an odd hole- Returns:
- Returns whether g has an odd hole or there is no shortest odd hole in C such that X is a near-cleaner for C.
-
hasConfigurationType1
Checks whether a graph has a configuration of type T1. A configuration of type T1 in g is a hole of length 5- Parameters:
g
- A Graph- Returns:
- whether g contains a configuration of Type T1 (5-cycle)
-
isYXComplete
A vertex y is X-complete if y contained in V(g)\X is adjacent to every vertex in X.- Parameters:
g
- A Graphy
- Vertex whose X-completeness is to assessx
- Set of vertices- Returns:
- whether y is X-complete
-
findAllAnticomponentsOfY
Returns all anticomponents of a graph and a vertex set.- Parameters:
g
- A Graphy
- A set of vertices- Returns:
- List of anticomponents of Y in g
-
hasConfigurationType2
Checks whether a graph is of configuration type T2. A configuration of type T2 in g is a sequence v1,v2,v3,v4,P,X such that:
- v1-v2-v3-v4 is a path of g
- X is an anticomponent of the set of all {v1,v2,v4}-complete vertices
- P is a path in G\(X+{v2,v3}) between v1,v4, and no vertex in P*, i.e. P's interior, is X-complete or adjacent to v2 or adjacent to v3
- Parameters:
g
- A Graph- Returns:
- whether g contains a configuration of Type T2
-
hasANeighbour
Reports whether v has at least one neighbour in set- Parameters:
g
- A Graphset
- A set of verticesv
- A vertex- Returns:
- whether v has at least one neighbour in set
-
findMaximalConnectedSubset
For each anticomponent X, find the maximal connected subset F' containing v5 with the properties that v1,v2 have no neighbours in F' and no vertex of F'\v5 is X-complete- Parameters:
g
- A GraphsetX
- A set of verticesv1
- A vertexv2
- A vertexv5
- A Vertex- Returns:
- The maximal connected vertex subset containing v5, no neighbours of v1 and v2, and no X-complete vertex except v5
-
hasANonneighbourInX
Reports whether a vertex has at least one nonneighbour in X- Parameters:
g
- A Graphv
- A VertexsetX
- A set of vertices- Returns:
- whether v has a nonneighbour in X
-
hasConfigurationType3
Checks whether a graph is of configuration type T3. A configuration of type T3 in g is a sequence v1,...,v6,P,X such that
- v1,...,v6 are distinct vertices of g
- v1v2,v3v4,v2v3,v3v5,v4v6 are edges, and v1v3,v2v4,v1v5,v2v5,v1v6,v2v6,v4v5 are non-edges
- X is an anticomponent of the set of all {v1,v2,v5}-complete vertices, and v3,v4 are not X-complete
- P is a path of g\(X+{v1,v2,v3,v4}) between v5,v6, and no vertex in P* is X-complete or adjacent to v1 or adjacent to v2
- if v5v6 is an edge then v6 is not X-complete
- Parameters:
g
- A Graph- Returns:
- whether g contains a configuration of Type T3
-
routine2
If true, the graph is not Berge. Checks whether g contains a Pyramid, Jewel, configuration type 1, 2 or 3.- Parameters:
g
- A Graph- Returns:
- whether g contains a pyramid, a jewel, a T1, a T2, or a T3
-
n
N(a,b) is the set of all {a,b}-complete vertices- Parameters:
g
- A Grapha
- A Vertexb
- A Vertex- Returns:
- The set of all {a,b}-complete vertices
-
r
r(a,b,c) is the cardinality of the largest anticomponent of N(a,b) that contains a nonneighbour of c (or 0, if c is N(a,b)-complete)- Parameters:
g
- a GraphnAB
- The set of all {a,b}-complete verticesc
- A vertex- Returns:
- The cardinality of the largest anticomponent of N(a,b) that contains a nonneighbour of c (or 0, if c is N(a,b)-complete)
-
y
Y(a,b,c) is the union of all anticomponents of N(a,b) that have cardinality strictly greater than r(a,b,c)- Parameters:
g
- A graphnAB
- The set of all {a,b}-complete verticesc
- A vertex- Returns:
- A Set of vertices with cardinality greater r(a,b,c)
-
w
W(a,b,c) is the anticomponent of N(a,b)+{c} that contains c- Parameters:
g
- A graphnAB
- The set of all {a,b}-complete verticesc
- A vertex- Returns:
- The anticomponent of N(a,b)+{c} containing c
-
z
Z(a,b,c) is the set of all (Y(a,b,c)+W(a,b,c))-complete vertices- Parameters:
g
- A graphnAB
- The set of all {a,b}-complete verticesc
- A vertex- Returns:
- A set of vertices
-
x
X(a,b,c)=Y(a,b,c)+Z(a,b,c)- Parameters:
g
- A graphnAB
- The set of all {a,b}-complete verticesc
- A vertex- Returns:
- The union of Y(a,b,c) and Z(a,b,c)
-
isTripleRelevant
A triple (a,b,c) of vertices is relevant if a,b are distinct and nonadjacent, and c is not contained in N(a,b) (possibly c is contained in {a,b}).- Parameters:
g
- A grapha
- A vertexb
- A vertexc
- A vertex- Returns:
- Assessement whether a,b,c is a relevant triple
-
routine3
Returns a set of vertex sets that may be near-cleaners for an amenable hole in g.- Parameters:
g
- A graph- Returns:
- possible near-cleaners
-
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 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, 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 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)
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 anti-hole 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.
-