1
$\begingroup$

According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. Unfortunately, neither the paper nor the references actually elaborate on what the algorithm is, beyond saying that you can modify the well-known algorithm for optimally coloring interval graphs (where you greedily color the graph in the order generated by sorting the intervals lexicographically) to compute the max clique. This makes sense, as the largest color used in an optimal coloring is the size of the max clique in a perfect graph (and interval graphs are perfect). Unfortunately, beyond that, I am lost as to how to compute the max clique. The obvious approach is to modify some data structure every time the max color increases, but I can't figure out precisely what data structure to use or how to modify it.

Does anyone know a reference for this algorithm or can reinvent a description of it?

$\endgroup$
3
  • $\begingroup$ Given an interval embedding, you can use a sliding window approach to find a maximum clique $\endgroup$ – narek Bojikian Jan 19 '20 at 22:32
  • $\begingroup$ I would say that the assumption of having an interval representation massively changes this question! It's non-trivial to find the interval representation (if it exists), but once you have it, the algorithm is basically a standard interview question! $\endgroup$ – Pål GD Jan 19 '20 at 22:49
  • $\begingroup$ An interval model of an interval graph can be computed in linear time, I believe the certificate yielded by the algorithm in people.mpi-inf.mpg.de/~mehlhorn/ftp/KMMS.pdf is precisely the interval model. I intended the input to be an interval model. $\endgroup$ – taktoa Jan 19 '20 at 23:07
1
$\begingroup$

Interval graphs are chordal graphs, so you can use a linear time algorithm for finding max clique in a chordal graph. This can be done by first finding a perfect elimination ordering, and then using the fact that every time a vertex is eliminated it forms a clique together with its neighbors that are not eliminated yet. Furthermore all maximal cliques appear in this process.

To find the perfect elimination ordering, maximum cardinality search (MCS) is the simplest algorithm and it works in linear time. (I don't know why Wikipedia mentions lexbfs first, it is much more complicated.)

$\endgroup$
3
  • $\begingroup$ This is contradicted by one of the statements in the paper I linked, which says that it is $\Omega(n \log n)$ to compute the max clique in an interval graph. $\endgroup$ – taktoa Jan 19 '20 at 23:03
  • $\begingroup$ I believe the fact that the intervals of an interval model form a perfect elimination ordering when sorted lexicographically is exploited by the algorithm in my answer, though. $\endgroup$ – taktoa Jan 19 '20 at 23:13
  • 1
    $\begingroup$ Your algorithm takes the interval model as an input, the algorithm that I mentioned takes the graph as an input. $\endgroup$ – Laakeri Jan 20 '20 at 0:34
0
$\begingroup$
def mex(m):
  for i in [0 ..]:
    if not(m.contains(i)):
      return i

def maxCliqueOfIntervals(intervals):
  maxClique = []
  map = {}
  for interval in intervals.sort():
    // map should only contain intervals that overlap with the current interval
    map.filter(lambda x: overlaps(x, interval));
    // choose the smallest color not in the map to color the current interval
    map.insert(mex(map), interval);
    // the map now comprises a clique, if it is larger than the current max clique,
    // replace the max clique with the current map
    if map.size() > maxClique.size():
      maxClique = map.elems();
  return maxClique;

I believe this is a correct implementation based on the interval coloring algorithm that runs in $O(n \log n)$ time.

If you just care about the max clique, then it can be simplified a bit:

def maxCliqueOfIntervals(intervals):
  maxClique = []
  active = []
  for interval in intervals.sort():
    active.filter(\x -> overlaps(x, interval));
    active.push(interval);
    if active.size() > maxClique.size():
      maxClique = active;
  return maxClique;
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.