Friday, April 12th, 2013 | 4pm-5pm | Burnside 920 |
Algorithms for deciding first order (FO) properties has attracted a significant amount of attention. In the case of graphs, FO properties include the existence of a subgraph or a dominating set of a fixed size. Classical results include the almost linear-time algorithm of Frick and Grohe which applies to graphs with locally bounded tree-width. In this talk, we briefly survey commonly applied techniques to design FPT algorithms for FO properties. We then focus on one class of graphs, intersection graphs of intervals with finitely many lengths, where the techniques do not seem to straightforwardly apply, and we design an FPT algorithm for deciding FO properties for this class of graphs. The talk contains results obtained during joint work with Ganian, Hlineny, Obdrzalek, Schwartz and Teska.