Variants of Merge-Width

Speaker(s)

Jakub Nowakowski

Language of the talk

English

Date

Aug. 21, 2026, 2:15 p.m.

Information about the event

CeNT I - Banacha 2C, room 01.48

Seminar

Seminar Algorithms

---

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.

---