A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced graph invariant called the twin-width is based on contraction sequences [BKTW, J. ACM ’22]. More precisely, if one puts error edges, henceforth red edges, between two vertices representing non-homogeneous subsets, the twin-width is the minimum integer d such that a contraction sequence, called d-sequence, exists that keeps red degree at most d. Many well-known graph classes are shown to have bounded twin-width including unit interval graphs, a strict hereditary class of permutation graphs, posets of bounded width, proper minor-closed class, subgraphs of O(1)-dimensional grids as well as graphs of bounded tree-width and clique-width. Since its introduction two years ago, twin-width gained extensive traction across areas such as graph theory, algorithms design, logic, data structure, constraint programming and communication complexity.
In this talk, we review some algorithmic implications of twin-width on graphs of bounded twin-width and beyond such graphs.
It was proved in [BKTW, JACM ’22] that FO (first-order) model-checking is fixed-parameter tractable provided that a d-sequence is given. This unifies and extends known tractability results. Due to its generality, the running time of FO model-checking algorithm suffers a huge dependency on the (nested) quantifier depth of the input sentence. It turns out that for concrete well-known problems such as k-Dominating Set, k-Independent Set and Subgraph Isomorphism in general, slick dynamic programming can be designed so that the runtime dependency is single exponential in k provided O(1)-sequence is given [BGKTW, ICALP ’21]. The spirit of such DP algorithms is further extended in [BKRT, SODA ’22] to attain an alternative proof for the tractability MSO model-checking on graph of bounded clique-width [Courcelle, Makowsky, Rotics, TCS ’00].
The terrain of monotone (closed under taking subgraphs) graph classes is fully charted in regards to fixed-parameter tractability of FO model-checking: a monotone graph class is nowhere dense if and only if FO model-checking is fpt on it. For the more general hereditary (closed under taking induced subgraphs) graph classes, it is conjectured that a class admits an fpt algorithm for FO model-checking if and only the class “does not encode all finite graphs in a manner interpretable by FO logic” (monadically dependent). We survey a few graph classes where the conjecture is positively affirmed and the dividing line is drawn precisely by the twin-width. Such classes include ordered graphs [BGdMST, STOC ’22], permutation graphs [BKTW, JACM ’22] and circle graphs [Hlinený, Filip Pokrývka, ’22], interval graphs and rooted directed path graphs [BCKKLT, ’22].
Twin-width can be useful for designing algorithms even on graph classes of unbounded twin-width. Some structures like large bicliques, half-graphs, or independent sets are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Combined with the FPT algorithm for FO model checking on graphs given with O(1)-sequences, this give rise to a variety of algorithmic win-win arguments [BCKKLT, ’22]. For instance, we readily derive fpt algorithms for k-Independent Set on visibility graphs of simple polygons, which was addressed as an open problem.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne