Deciding Properties in Sparse Combinatorial Structures
Algorithmic metatheorems guarantee that certain types of problems have efficient algorithms. A classical example is the result of Courcelle asserting that every MSOL property can be tested in linear time for graphs with bounded tree-width. We focus on simpler properties, those expressible in first order logic (FOL); our main result asserts that every FOL property can be decided in linear time for graphs in a class with bounded expansion. Such classes include graphs with bounded maximum degree or proper-minor closed classes of graphs. \newline\indent The talk is based on joint work with Zdenek Dvorak and Robin Thomas.