<p>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.</p>
<p>Are there similar results for (<span class="math-container">$k$</span>-uniform) hypergraphs, when viewing a hypergraph as as structure equipped with a <span class="math-container">$k$</span>-ary relation symbol <span class="math-container">$E$</span>? If so, can you point me to the according literature?</p>

CC BY-SA 4.0
2022-05-17T15:54:11.170Z
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.
Sylvain
CC BY-SA 4.0
2022-05-18T10:04:12.250Z
@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?
Reijo Jaakkola
CC BY-SA 4.0
2022-05-18T10:12:36.627Z
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 (https://hal.inria.fr/tel-01963540/document).
Sylvain
CC BY-SA 4.0
2022-05-18T10:31:55.623Z
@Sylvain Why not post that comment as an answer? It answers precisely the question that the OP had.
Reijo Jaakkola
<cc.complexity-theory><reference-request><lo.logic><hypergraphs><first-order-logic>
Are there classes for that FO-model checking is FPT on hypergraphs?
embie27
# Are there classes for that FO-model checking is FPT on hypergraphs?

(Asked by: username_0 on 2022-05-17)

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?

**Tags:** cc.complexity-theory, reference-request, lo.logic, hypergraphs, first-order-logic

> **Comments:**
> **username_1**: 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.  
> **username_2**: @username_1 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?  
> **username_1**: 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 (https://hal.inria.fr/tel-01963540/document).  
> **username_2**: @username_1 Why not post that comment as an answer? It answers precisely the question that the OP had.  

---

## 0 answers

