Can I read First-Order Model Checking on Monadically Stable Graph Classes on EtoBox?

First-Order Model Checking on Monadically Stable Graph Classes by Dreier, Jan; Eleftheriadis, Ioannis; Mählmann, Nikolas; McCarty, Rose; Pilipczuk, Michał; Toruńczyk, Szymon is a scholarly article available to read on EtoBox.

What is First-Order Model Checking on Monadically Stable Graph Classes about?

A graph class $\mathscr{C}$ is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from $\mathscr{C}$. We prove that the model checking problem for first-order logic is fixed-parameter tractable on every monadically stable graph class. This extends the results of [Grohe, Kreutzer, and Siebertz; J. ACM '17] for nowhere dense classes and of [Dreier, M\"ahlmann, and Siebertz; STOC '23] for structurally nowhere dense classes to all monadically stable classes. As a complementary hardness result, we prove that for every hereditary graph class $\mathscr{C}$ that is edge-stable (excludes some half-graph as a semi-induced subgraph) but not monadically stable, first-order model checking is $\mathrm{AW}[*]$-hard on $\mathscr{C}$, and $\mathrm{W}[1]$-hard when restricted to existential sentences. This confirms, in the special case of edge-stable classes, an on-going conjecture that the notion of monadic NIP delimits the tractability of first-order model checking on hereditary classes of graphs. For our tractability result, we first prove that monadically stable graph classes have almost linear neighborhood complexity. Using t

Author

Dreier, Jan; Eleftheriadis, Ioannis; Mählmann, Nikolas; McCarty, Rose; Pilipczuk, Michał; Toruńczyk, Szymon

Published

2023

Language

EN