Algorithmic metatheorems
Algorithmic metatheorems guarantee that certain types of problems have efficient algorithms. A classical example is the theorem of Courcelle asserting that every MSOL property can be tested in linear time for graphs with bounded tree-width. In this talk, we survey existing results on testing MSOL and FOL properties for various classes of combinatorial structures, graphs and matroids in particular, and present their relation to graph homomorpisms. Among others we mention our recent result with Tomas Gavenciak and Sang-il Oum on matroids with locally bounded branch width and our result with Zdenek Dvorak and Robin Thomas on testing FOL properties in graphs with (locally) bounded expansion. The latter result will be discussed in more detail in the talk of Zdenek Dvorak.