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.

  • Field Details

    • certificate

      private GraphPath<V,E> certificate
    • certify

      private boolean certify
  • Constructor Details

    • BergeGraphInspector

      public BergeGraphInspector()
  • Method Details

    • intersectGraphPaths

      private List<V> intersectGraphPaths(GraphPath<V,E> p1, GraphPath<V,E> p2)
      Lists the vertices which are covered by two paths
      Parameters:
      p1 - A Path in g
      p2 - 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 Graph
      pathS - A Path in g
      pathT - A Path in g
      m - A vertex
      b1 - A base vertex
      b2 - A base vertex
      b3 - A base vertex
      s1 - A vertex
      s2 - A vertex
      s3 - A vertex
      Returns:
      The conjunct path of S and T
    • bfOddHoleCertificate

      private void bfOddHoleCertificate(Graph<V,E> g)
    • containsPyramid

      boolean containsPyramid(Graph<V,E> g)
      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

      private List<Set<V>> findAllComponents(Graph<V,E> g, Set<V> f)
      Finds all Components of a set F contained in V(g)
      Parameters:
      g - A graph
      f - A vertex subset of g
      Returns:
      Components of F in g
    • containsJewel

      boolean containsJewel(Graph<V,E> g)
      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

      boolean containsCleanShortestOddHole(Graph<V,E> g)
      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

      private GraphPath<V,E> getPathAvoidingX(Graph<V,E> g, V start, V end, Set<V> x)
      Returns a path in g from start to end avoiding the vertices in X
      Parameters:
      g - A Graph
      start - start vertex
      end - end vertex
      x - set of vertices which should not be in the graph
      Returns:
      A Path in G\X
    • containsShortestOddHole

      private boolean containsShortestOddHole(Graph<V,E> g, Set<V> x)
      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 jewel
      x - 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

      private boolean routine1(Graph<V,E> g, Set<V> x)
      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 jewel
      x - 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

      private boolean hasConfigurationType1(Graph<V,E> g)
      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

      boolean isYXComplete(Graph<V,E> g, V y, Set<V> x)
      A vertex y is X-complete if y contained in V(g)\X is adjacent to every vertex in X.
      Parameters:
      g - A Graph
      y - Vertex whose X-completeness is to assess
      x - Set of vertices
      Returns:
      whether y is X-complete
    • findAllAnticomponentsOfY

      private List<Set<V>> findAllAnticomponentsOfY(Graph<V,E> g, Set<V> y)
      Returns all anticomponents of a graph and a vertex set.
      Parameters:
      g - A Graph
      y - A set of vertices
      Returns:
      List of anticomponents of Y in g
    • hasConfigurationType2

      boolean hasConfigurationType2(Graph<V,E> g)

      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
      An example is the complement graph of a cycle-7-graph
      Parameters:
      g - A Graph
      Returns:
      whether g contains a configuration of Type T2
    • hasANeighbour

      private boolean hasANeighbour(Graph<V,E> g, Set<V> set, V v)
      Reports whether v has at least one neighbour in set
      Parameters:
      g - A Graph
      set - A set of vertices
      v - A vertex
      Returns:
      whether v has at least one neighbour in set
    • findMaximalConnectedSubset

      private Set<V> findMaximalConnectedSubset(Graph<V,E> g, Set<V> setX, V v1, V v2, V v5)
      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 Graph
      setX - A set of vertices
      v1 - A vertex
      v2 - A vertex
      v5 - A Vertex
      Returns:
      The maximal connected vertex subset containing v5, no neighbours of v1 and v2, and no X-complete vertex except v5
    • hasANonneighbourInX

      private boolean hasANonneighbourInX(Graph<V,E> g, V v, Set<V> setX)
      Reports whether a vertex has at least one nonneighbour in X
      Parameters:
      g - A Graph
      v - A Vertex
      setX - A set of vertices
      Returns:
      whether v has a nonneighbour in X
    • hasConfigurationType3

      boolean hasConfigurationType3(Graph<V,E> g)

      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

      private boolean routine2(Graph<V,E> g)
      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

      private Set<V> n(Graph<V,E> g, V a, V b)
      N(a,b) is the set of all {a,b}-complete vertices
      Parameters:
      g - A Graph
      a - A Vertex
      b - A Vertex
      Returns:
      The set of all {a,b}-complete vertices
    • r

      private int r(Graph<V,E> g, Set<V> nAB, V c)
      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 Graph
      nAB - The set of all {a,b}-complete vertices
      c - 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

      private Set<V> y(Graph<V,E> g, Set<V> nAB, V 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)
      Parameters:
      g - A graph
      nAB - The set of all {a,b}-complete vertices
      c - A vertex
      Returns:
      A Set of vertices with cardinality greater r(a,b,c)
    • w

      private Set<V> w(Graph<V,E> g, Set<V> nAB, V c)
      W(a,b,c) is the anticomponent of N(a,b)+{c} that contains c
      Parameters:
      g - A graph
      nAB - The set of all {a,b}-complete vertices
      c - A vertex
      Returns:
      The anticomponent of N(a,b)+{c} containing c
    • z

      private Set<V> z(Graph<V,E> g, Set<V> nAB, V c)
      Z(a,b,c) is the set of all (Y(a,b,c)+W(a,b,c))-complete vertices
      Parameters:
      g - A graph
      nAB - The set of all {a,b}-complete vertices
      c - A vertex
      Returns:
      A set of vertices
    • x

      private Set<V> x(Graph<V,E> g, Set<V> nAB, V c)
      X(a,b,c)=Y(a,b,c)+Z(a,b,c)
      Parameters:
      g - A graph
      nAB - The set of all {a,b}-complete vertices
      c - A vertex
      Returns:
      The union of Y(a,b,c) and Z(a,b,c)
    • isTripleRelevant

      private boolean isTripleRelevant(Graph<V,E> g, V a, V b, V c)
      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 graph
      a - A vertex
      b - A vertex
      c - A vertex
      Returns:
      Assessement whether a,b,c is a relevant triple
    • routine3

      Set<Set<V>> routine3(Graph<V,E> g)
      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

      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