Inspired by a width 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, map graphs, -free unit -dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of -contractions, witness that the twin-width is at most . We show that FO model checking, that is deciding if a given first-order formula evaluates to true for a given binary structure on a domain , is FPT in on classes of bounded twin-width, provided the witness is given. More precisely, being given a -contraction sequence for , our algorithm runs in time where is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS ’15].
In order to explore the limits of twin-width, we generalize to bounded twin-width classes a result by Norine et al. [JCTB ’06] stating that proper minor-free classes are small (i.e., they contain at most graphs on vertices, for some constant ). This implies by a counting argument that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width.
Joint work with Stéphan Thomassé, Édouard Bonnet, and Rémi Watrigant.