# Are there classes for that FO-model checking is FPT on hypergraphs?

For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al.

Are there similar results for ($$k$$-uniform) hypergraphs, when viewing a hypergraph as as structure equipped with a $$k$$-ary relation symbol $$E$$? If so, can you point me to the according literature?

• Such FPT results for FO model-checking on classes of graphs can be lifted to classes of finite relational structures, by interpreting each structure into a (possibly coloured) graph. May 17 at 15:54
• @Sylvain Care to elaborate on that? What properties does a class of finite relational structures need to have so that I can encode this class as some class of graphs for which the FO MC is in FPT? References? May 18 at 10:04
• Because it's sort of a folklore argument, most papers do not include an explanation. Here is one place I remember it being explicit: Section 4.3 of Alexandre Vigny's PhD thesis (hal.inria.fr/tel-01963540/document). May 18 at 10:12
• @Sylvain Why not post that comment as an answer? It answers precisely the question that the OP had. May 18 at 10:31