Variants of Merge-Width

Prelegent(ci)

Jakub Nowakowski

Język referatu

angielski

Termin

21 sierpnia 2026 14:15

Informacje na temat wydarzenia

CeNT I - Banacha 2C, sala 01.48

Seminarium

Seminarium "Algorytmika"

---

Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We explore this notion further, proving the equivalence of several its alternative definitions. 

This talk is mostly focused on our characterisation via definable merge-width, which uses vertex orderings inspired by generalised colouring numbers from sparsity theory. It enables us to obtain the first nontrivial approximation algorithm for merge-width parameters, running in time n^(O(1))·2^n, and to also obtain a new characterisation of bounded clique-width in terms of vertex orderings.

The talk is based on the article https://arxiv.org/abs/2602.23867, which is joint work with Karolina Drabik, Maël Dumas, Colin Geniet, Michał Pilipczuk and Szymon Toruńczyk.

---