New clique and independent set algorithms for circle graphs (Q1186158)

The authors present efficient algorithms for finding a maximum clique and a maximum independent set of a circle graph. A circle graph is a graph representing intersecting chords of a circle, or, equivalently, intersecting intervals of a line which are not contained one within another. Given the interval model of the graph the proposed algorithms improve over the running time of the best previously known algorithms. If the circle graph has \(n\) nodes and \(e\) edges, then a maximum clique of cardinality \(c\), a maximum weighted clique, and a maximum weighted independent set can be found, respectively, in time \(O(n\log n+ \min\{e,nc\log(2n/c)\})\), \(O(n\log n+ \min\{n^ 2,e\log\log n\})\), and \(O(n\log n+ dn)\), where \(d\) is the maximum number of intervals crossing any position of the line in the interval model of the graph. Some algorithms solve the problems by reducing them to that of repeatedly finding longest or heaviest chains in suitably defined partially ordered sets. Summarizing, the paper is both interesting and well written, and introduces new techniques to solve the problems.