Edouard Bonnet. Twin-width скачать в хорошем качестве

Edouard Bonnet. Twin-width

Talks on Frontiers of Parameterized Complexity https://frontpc.blogspot.com Keywords: Twin-width, contraction sequence, chi-boundedness, Erdos-Hajnal, FO model checking October 01, 2020 Edouard Bonnet, Universite Claude Bernard Lyon Title: Twin-width Abstract: Inspired by an invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. 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.