The link to join the zoom talk is https://uib.zoom.us/j/
Meeting ID: 423 116 9675
Password: Name of the W-complete problem, six letters, all capital. Set of pairwise adjacent vertices.
Proper minor-closed classes, bounded rank-width graphs, $K_t$-free unit ball graphs, posets with bounded-size antichains, proper subclasses of permutation graphs, and some cubic expanders based on repeated 2-lifts, all have bounded twin-width. On all these classes we can compute in polynomial time a d-contraction sequence, witness that the twin-width is at most d. FO model checking asks if a given first-order sentence $\phi$ is true on a given structure G. We show that this problem is FPT in parameter $|\phi|$ on classes of bounded twin-width binary structures, provided the witness is given. More precisely, given a d-contraction sequence for G, our algorithm runs in time $f(d,|\phi|) |V(G)|$ where f is a computable but non-elementary function. Practical algorithms do exist for typical FO expressible problems, like k-Independent Set and k-Dominating Set. Furthermore twin-width is robust as far as first-order logic is concerned: any transduction of a bounded twin-width class has bounded twin-width. Bounded twin-width classes have other interesting properties: they are small, $\chi$-bounded, satisfy the strong Erdos-Hajnal property, and their intersection with the sparse world has many equivalent characterizations.
We will survey our current understanding of twin-width, putting the emphasis on fixed-parameter tractability of FO model checking and intriguing/pressing open questions.
This is joint work with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.