FO model checking of interval graphs

We study the computational complexity of the model checking problem for the first order (FO) logic on interval graphs, i. e. , interscetion graphs of intervals on the real line. As the main result we show that for n-vertex interval graphs this problem can be solved in time O(n log n) if we take intervals with lengths from a fixed finite set. On the other hand, we show that this is no longer true once the interval lengths taken from any set that is dense in some open subset.

Authors

• Robert Ganian Algorithms and Complexity Group, TU Wien, Vienna, Austria
• Petr Hliněný
• Daniel Kral
• Jan Obdržálek
• Jarett Schwartz
• Jakub Teska

Keywords

No keywords are indexed for this paper.