4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    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$
    – Reijo Jaakkola
    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
    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$
    – Reijo Jaakkola
    May 18, 2022 at 10:31

0

Reset to default

Your Answer

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