English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

A graph class $\mathscr{C}$ is called monadically stable if one cannotinterpret, in first-order logic, arbitrary large linear orders in coloredgraphs from $\mathscr{C}$. We prove that the model checking problem forfirst-order logic is fixed-parameter tractable on every monadically stablegraph 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 graphclass $\mathscr{C}$ that is edge-stable (excludes some half-graph as asemi-induced subgraph) but not monadically stable, first-order model checkingis $\mathrm{AW}[*]$-hard on $\mathscr{C}$, and $\mathrm{W}[1]$-hard whenrestricted to existential sentences. This confirms, in the special case ofedge-stable classes, an on-going conjecture that the notion of monadic NIPdelimits the tractability of first-order model checking on hereditary classesof graphs.  For our tractability result, we first prove that monadically stable graphclasses have almost linear neighborhood complexity. Using this, we constructsparse neighborhood covers for monadically stable classes, which provides themissing ingredient for the algorithm of [Dreier, M\"ahlmann, and Siebertz; STOC'23]. The key component of this construction is the usage of orders with lowcrossing number [Welzl; SoCG '88], a tool from the area of range queries.  For our hardness result, we prove a new characterization of monadicallystable graph classes in terms of forbidden induced subgraphs. We then use thischaracterization to show that in hereditary classes that are edge-stable butnot monadically stable, one can effectively interpret the class of all graphsusing only existential formulas.

First-Order Model Checking on Monadically Stable Graph Classes