Show simple item record

Twin-width II: small classes

dc.contributor.authorBonnet, Edouard
dc.contributor.authorGeniet, Colin
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung
dc.contributor.authorThomassé, Stéphan
dc.contributor.authorWatrigant, Rémi
dc.date.accessioned2021-11-16T11:37:09Z
dc.date.available2021-11-16T11:37:09Z
dc.date.issued2021
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22214
dc.language.isoenen
dc.subjectTwin-widthen
dc.subjectsmall classesen
dc.subjectexpandersen
dc.subjectclique subdivisionsen
dc.subjectsparsityen
dc.subject.ddc005en
dc.titleTwin-width II: small classesen
dc.typeCommunication / Conférence
dc.description.abstractenThe 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.en
dc.identifier.citationpages1977–1996en
dc.relation.ispartofpublnameACM - Association for Computing Machineryen
dc.relation.ispartofpublcityNew York, NYen
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-1-61197-646-5en
dc.relation.conftitleSODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithmsen
dc.relation.confdate2021-01
dc.relation.confcityonlineen
dc.relation.confcountryUnited Statesen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2021-11-16T11:33:52Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
2006.09877.pdf
Size:
796.0Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record