Bounding twin-width using red potential

Jakub Balabán, 5 Dec 2022

Twin-width is a parameter of graphs and other relational structures (similar, for example, to treewidth), introduced in 2020 by Bonnet et al. One of their key results is that FO model checking is \(\mathsf{FPT}\) on classes of bounded twin-width, given a certificate of the boundedness. They also bounded the twin-width of posets of bounded width. However, their double-exponential bound was very loose (which affects the runtime of twin-width-based algorithms). We improved this bound down to linear using a simple combinatorial method, so-called red potential method. Later we used this method also for efficiently bounding the twin-width of proper \(k\)-mixed-thin graphs, which largely generalize proper interval graphs. In this presentation, I would like to explain the red potential method, which can hopefully be used to efficiently bound the twin-width of other classes, too.