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
TypeCommunication / Conférence
Conference titleSODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
Conference countryUnited States
MetadataShow full item record
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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 / KeywordsTwin-width; small classes; expanders; clique subdivisions; sparsity
Showing items related by title and author.
Bonamy, Marthe; Bonnet, Edouard; Bousquet, Nicolas; Charbit, Pierre; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, P.; Sikora, Florian; Thomassé, S. (2021) Article accepté pour publication ou publié