When FO properties are efficiently solvable on interval graphs
Presented by Dr. Petr HLINěNý
Type: Oral presentation
Track: Discrete and Computational Geometry
FO (first-order logic) properties include, for instance, the dominating set and subgraph isomorphism problems. We investigate the question, on which subclasses of interval graphs these problems have efficient (parameterized) algorithms--while this is the case of unit interval graphs, no such general algorithmic metatheorem is possible on all interval graphs. We prove that fixed-parameter tractability of FO holds on interval representations using any finite set of interval lengths, but cannot be true when any infinite dense set of lengths is allowed.