Merge-width and First-Order Model Checking

Speaker(s)

Szymon Toruńczyk

Affiliation

University of Warsaw

Language of the talk

English

Date

Nov. 13, 2024, 2:15 p.m.

Room

room 5440

Title in Polish

Merge-width and First-Order Model Checking

Seminar

Seminar Automata Theory

---

We introduce merge-width, a family of graph parameters that unifies several structural graph measures, including treewidth, degeneracy, twin-width, clique-width, and generalized coloring numbers. Graph classes of bounded merge-width – for which the radius-r merge-width parameter is bounded by a constant for each r –  include all classes of bounded expansion or of bounded twin-width, thus unifying two central notions from the Sparsity and Twin-width frameworks. Furthermore, they are preserved under first-order transductions, which attests to their robustness.

As our main result, we show that the model checking problem for first-order logic is fixed-parameter tractable on graph classes of bounded merge-width, assuming the input includes a witnessing merge sequence. This unites and extends two previous model checking results: the result of Dvorak, Kral, and Thomas for classes of bounded expansion, and the result of Bonnet, Kim, Thomasse, and Watrigant for classes of bounded twin-width.

 

Joint work with Jan Dreier.

---