
Twin-width II: small classes
Bonnet, Edouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021), Twin-width II: small classes, SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2021-01, online, United States
View/ Open
Type
Communication / ConférenceDate
2021Conference title
SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete AlgorithmsConference date
2021-01Conference city
onlineConference country
United StatesPublisher
ACM - Association for Computing Machinery
Published in
New York, NY
ISBN
978-1-61197-646-5
Pages
1977–1996
Metadata
Show full item recordAuthor(s)
Bonnet, EdouardGeniet, Colin
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Thomassé, Stéphan
Watrigant, Rémi
Abstract (EN)
The twin-width of a graph G is the minimum integer d such that G has a d-contraction sequence, that is, a sequence of |V(G)|−1 iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most d, where a red edge appears between two sets of identified vertices if they are not homogeneous in G. We show that if a graph admits a d-contraction sequence, then it also has a linear-arity tree of f(d)-contractions, for some function f. First this permits to show that every bounded twin-width class is small, i.e., has at most n!cn graphs labeled by [n], for some constant c. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. The second consequence is an O(logn)-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the "small conjecture" that, conversely, every small hereditary class has bounded twin-width. Inspired by sorting networks of logarithmic depth, we show that logΘ(loglogd)n-subdivisions of Kn (a small class when d is constant) have twin-width at most d. We obtain a rather sharp converse with a surprisingly direct proof: the logd+1n-subdivision of Kn has twin-width at least d. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from K4~[Bilu and Linial, Combinatorica '06] have bounded twin-width, too. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width and discuss how it compares with other sparse classes.Subjects / Keywords
Twin-width; small classes; expanders; clique subdivisions; sparsityRelated 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; Geniet, Colin; Thomassé, Stéphan; Watrigant, Rémi (2022) Article accepté pour publication ou publié
-
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, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021) Article accepté pour publication ou publié