TITLE: Algorithms for FO model checking
SPEAKER: Daniel Kral (University of Warwick)

ABSTRACT:

Properties of relational structures that can be described
in the first order (FO) logic belong among the simplest ones
but yet many algorithmic questions related to them are
challenging. In this talk, we focus on deciding FO properties
for graphs. Such properties include e.g. the existence of
a subgraph or a dominating set of a fixed size. Every
FO property can can be decided in polynomial time but
the desire is to construct FPT algorithms, i.e., algorithms
with the degree of the polynomial in the running time estimate
independent of an FO property.

Classical results on deciding FO properties include the almost
linear-time algorithm of Frick and Grohe for graphs with locally
bounded tree-width. In the talk, we first 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.