Merge-width and First-Order Model Checking

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

13 listopada 2024 14:15

Pokój

p. 5440

Tytuł w języku polskim

Merge-width and First-Order Model Checking

Seminarium

Seminarium „Teoria automatów”

---

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.

---