2026-07-20T14:51:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25531 2026-03-19T13:34:36Z ddc:004 open_access

Computing Twin-Width via Treedepth and Vertex Integrity Ganian, Robert Rocton, Mathis twin-width fixed-parameter algorithms treedepth vertex integrity Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorithmic importance, computing twin-width remains poorly understood: even recognizing graphs of twin-width at most four is NP-hard, and no fixed-parameter approximations parameterized by twin-width itself are known. A recent approach towards breaking this barrier focuses on first developing fixed-parameter algorithms for computing or approximating twin-width under parameterizations distinct from twin-width. Our first result establishes that approximating twin-width is fixed-parameter tractable when parameterized by treedepth, thereby breaking the long-standing barrier that all previous tractable parameterizations were based on deletion distance. The proof proceeds via oriented twin-width, yielding the first constructive evidence that this variant may be easier to handle algorithmically. As our second main result, we show that computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Ganian and Mathis Rocton 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.42 urn:nbn:de:0030-drops-255318 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.42 eng https://creativecommons.org/licenses/by/4.0/legalcode