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

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.

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.