Twinwidth VI: the lens of contraction sequences
Bonnet, Edouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan (2022), Twinwidth VI: the lens of contraction sequences, ACMSIAM Symposium on Discrete Algorithms (SODA22), 202201
View/Open
Type
Communication / ConférenceDate
2022Conference title
ACMSIAM Symposium on Discrete Algorithms (SODA22)Conference date
202201Metadata
Show full item recordAuthor(s)
Bonnet, EdouardLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Reinald, Amadeus
Thomassé, Stéphan
Abstract (EN)
A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twinwidth graph invariant is based on contraction sequences. More precisely, if one puts error edges, henceforth red edges, between two vertices representing nonhomogeneous subsets, the twinwidth is the minimum integer d such that a contraction sequence exists that keeps red degree at most d. By changing the condition imposed on the trigraphs (i.e., graphs with some edges being red) and possibly slightly tweaking the notion of contractions, we show how to characterize the wellestablished bounded rankwidth, treewidth, linear rankwidth, pathwidthusually defined in the framework of branchdecompositions, and proper minorclosed classes by means of contraction sequences. Contraction sequences hold a crucial advantage over branchdecompositions: While one can scale down contraction sequences to capture classical width notions, the more general bounded twinwidth goes beyond their scope, as it contains planar graphs in particular, a class with unbounded rankwidth. As an application we give a transparent alternative proof of the celebrated Courcelle's theorem (actually of its generalization by Courcelle, Makowsky, and Rotics), that MSO2 (resp. MSO1) model checking on graphs with bounded treewidth (resp. bounded rankwidth) is fixedparameter tractable in the size of the input sentence. We are hopeful that our characterizations can help in other contexts. We then explore new avenues along the general theme of contraction sequences both in order to refine the landscape between bounded treewidth and bounded twinwidth (via spanning twinwidth) and to capture more general classes than bounded twinwidth. To this end, we define an oriented version of twinwidth, where appearing red edges are oriented away from the newly contracted vertex, and the mere red outdegree should remain bounded. Surprisingly, classes of bounded oriented twinwidth coincide with those of bounded twinwidth. This greatly simplifies the task of showing that a class has bounded twinwidth. As an example, using a lemma by Norine, Seymour, Thomas, and Wollan, we give a 5line proof that Ktminor free graphs have bounded twinwidth. Without oriented twinwidth, this fact was shown by a somewhat intricate 4page proof in the first paper of the series. Finally we explore the concept of partial contraction sequences, instead of terminating on a singlevertex graph, the sequence ends when reaching a particular target class. We show that FO model checking (resp. ∃FO model checking) is fixedparameter tractable on classes with partial contraction sequences to a class of bounded degree (resp. bounded expansion), provided such a sequence is given. Efficiently finding such partial sequences could turn out simpler than finding a (complete) sequence.Subjects / Keywords
Twinwidth; contraction sequences; width parameters; FO and MSO modelchecking; matroidsRelated items
Showing items related by title and author.

Bonnet, Edouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021) Communication / Conférence

Bonnet, Edouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan; Watrigant, Rémi (2021) Communication / Conférence

Bonnet, Edouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2020) Communication / Conférence

Bonnet, Edouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021) Communication / Conférence

Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021) Article accepté pour publication ou publié