2
$\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$ Jan 19, 2020 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, 2020 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, 2020 at 23:07

2 Answers 2

2
$\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, 2020 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, 2020 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, 2020 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$
2
  • $\begingroup$ This can take O(n^2) time if e.g. the intervals are strictly nested. You should iterate over the sorted endpoints (labeled with start/end). Then you only need to do constant work per endpoint. Use 1 pass for the size of the max clique, and another pass to get the clique itself. $\endgroup$ Aug 2 at 7:07
  • $\begingroup$ Yeah, I was assuming that the input is normalized, i.e.: does not contain any strictly nested intervals. I suppose that makes this an O(n log n) algorithm for finding max clique in a model of a proper interval graph. $\endgroup$
    – taktoa
    Aug 3 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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