5
$\begingroup$

I have implemented a comparability graph recognition algorithm from M.C. Golumbic's "Algorithmic graph theory and perfect graphs" book. It is hinted in Fekete, Schepers, and van der Veen's "Exact Algorithm for Higher-Dimensional Orthogonal Packing" paper that the algorithm can be modified such that given the negative recognition result you can obtain a two-chordless cycle. But it is not explained how it is done and my knowledge on graph theory isn't anything special.

My current intuition is that if the recognition algorithm fails at level $k$ then a cycle must have been created where a transitive orientation is not possible. And this would mean the set of edges at the point of failure at level $k$ would induce a subgraph that contains the cycle I'm looking for, and then I just need to prune away the edges that have no involvment with the cycle created.

My questions: Is my intuition correct and if not, what does Fekete, Schepers, and van der Veen's "simple to modify" hint mean?

I'm doing this for efficiency, I want to obtain two results with one algorithmic search.

import networkx as nx

def comparability(G):
  classification = dict()
  k = 0 
  def explore(i, j): 
    # k and classification from outer function
    adjacent_I = set(G.neighbors(i))
    adjacent_J = set(G.neighbors(j))
    classtest = lambda e: e in classification and abs(classification[e]) != k
    for m in adjacent_I:
      if m not in adjacent_J or classtest((j, m)):
        if (i, m) not in classification:
          classification[(i, m)] = k 
          classification[(m, i)] = -k
          if not explore(i, m): 
            return False
        elif (i, m) in classification and classification[(i, m)] == -k: 
          return False
    for m in adjacent_J:
      if m not in adjacent_I or classtest((i, m)):
        if (m, j) not in classification:
          classification[(m, j)] = k 
          classification[(j, m)] = -k
          if not explore(m, j): 
            return False
        elif (m, j) in classification and classification[(m, j)] == -k: 
          return False
    return True
  for i, j in G.edges():
    if (i, j) not in classification:
      k += 1
      classification[(i, j)] = k 
      classification[(j, i)] = -k
      if not explore(i, j): 
        return False, classification
  return True, classification

G = nx.Graph()
G.add_nodes_from([1,2,3,4])
G.add_edges_from([(1,2),(1,3),(1,4),(3,4)])
print comparability(G) # True

G = nx.Graph()
G.add_nodes_from([1,2,3,4,5,6])
G.add_edges_from([(1,2),(2,3),(2,4),(3,4),(3,5),(4,6)])
print comparability(G) # False
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.