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?

  • 4
    $\begingroup$ 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. $\endgroup$
    – Sylvain
    Commented May 17, 2022 at 15:54
  • $\begingroup$ @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? $\endgroup$ Commented May 18, 2022 at 10:04
  • $\begingroup$ 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). $\endgroup$
    – Sylvain
    Commented May 18, 2022 at 10:12
  • 1
    $\begingroup$ @Sylvain Why not post that comment as an answer? It answers precisely the question that the OP had. $\endgroup$ Commented May 18, 2022 at 10:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.