Twin-width IV and V: ordered structures, modular counting and matrix multiplication
Abstract: Twin-width is a graph parameter recently discovered by Bonnet, Kim, Thomassé and Watrigant that aims at generalizing and unifying many previous notions from parameterized complexity. The original article introducing twin-width was the starting point of a series of papers setting the basis of the theory of twin-width.
In this presentation, I will first give you a brief introduction to twin-width, and state the main results and questions. Then I will focus on ordered graphs, (i.e. graphs with a total order on their vertices) and show you that in this case there are many different ways to characterize twin-width boundedness, going from enumerative combinatorics to logics. In particular, from these characterizations we will see that there exists an FPT-algorithm to approximate the twin-width of ordered graphs, which is still not known to exist in the general case. In the remaining time, as an example of application I will explain you how to derive an efficient algorithm to compute in time Oq,t(n2 log(n)) the product of two matrices of twin-width t over the finite field Fq.
Joint work with Edouard Bonnet, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé and Szymon Toruńczyk.