Alternative to Bron-Kerbosch algorithm for enumerating maximal cliques in inverse interval graphs

Question

I often use inverse interval graphs to represent biologically relevant features along a genomic sequence. For example, given a (relatively) small genomic region, the graph would contain a node for each gene in the region, and there would be an edge between two nodes if the corresponding genes do not overlap (the complement of the interval graph).

I recently implemented a program that uses the Bron-Kerbosch algorithm to list all maximal cliques for an inverse interval graph corresponding to a small genomic region. This algorithm has an exponential complexity, but I didn't worry about it at first since I didn't expect more than a handful of genes to be present in a given region. However, I have since encountered a few cases in my data that the Bron-Kerbosch algorithm cannot handle in a reasonable amount of time or space.

This Wikipedia article mentions several alternatives to the Bron-Kerbosch algorithm that have a polynomial complexity as long as the number of cliques is polynomially bounded. I have begun looking into Chiba & Nishizeki's algorithm as a possible alternative, but the formulation is very dense. Before I spend too much time looking into this, I wanted to ask two questions.

1. First, since my graph is an inverse interval graph and not an interval graph, am I actually guaranteed polynomial runtime with these alternative algorithms?
2. Second, assuming I do want to implement one of these alternative algorithms, do any of them have available reference implementations? I don't expect a reference implementation to work out of the box with my problem, but it would be extremely helpful when trying to adapt the algorithm for my program.

Answer 1

This question is two month old but I'll add information anyway.

1. Chiba & Nishizeki's algorithm is for any arbitrary graph so the complexity is guaranteed for any class of graph. It is hinted in this paper that Chiba & Nishizeki's algorithm actually performs quite poor compared to the modified and optimized versions of Bron-Kerbosch algorithm. Of cause this could be because their implementation is poor or the data set they used.

2. The paper is usually the reference implementation, off the top of my head I don't know of any great libraries, I'm usually a hand coder type of guy.

If you take into account that a maximal independent set in some graph, it is a maximal clique in the complementary graph. You can implement maximal independent set enumeration on the interval graph instead. D.S. Johnson's "On generating all maximal independent sets" has a nice and clear explanation of his polynomial delay algorithm.

Also $\text{co-interval} \equiv \text{co-chordal} \cap \text{comparability}$, you may be able to take advantage that you are using $\text{comparability}$ graph. If you don't need to enumerate maximal cliques and you only need a single instance (I known nothing about genomic sequences) then an efficient max weight clique algorithm (chapter 5 section 7) exist for $\text{comparability}$ graphs.