Maximum independent set and maximum clique algorithms for overlap graphs

摘要

We give polynomial time algorithms for the maximum independent set and maximum clique problems for classes of overlap graphs, assuming an overlap model is provided as input. The independent set algorithm applies to any class of overlap graphs for which the maximum weight independent set problem is polynomially solvable on the corresponding intersection graph class, where the vertex weights are nonnegative integers on which arithmetic operations can be performed in constant time. The maximum clique algorithm requires only that the overlap model satisfy the Helly property. In both cases, the size of the overlap model must be bounded by a polynomial in the size of the graph. The conditions for both algorithms are satisfied by the class of overlap graphs of subtrees in a tree, which contains chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs.