Friday, April 12th, 2013 4pm-5pm Burnside 920
Mathematics Institute, University of Warwick
Algorithms for FO model checking

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.

Winter 2013 Schedule