2026-08-06T10:27:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19717 2024-03-11T06:37:03Z ddc:004 open_access

Computing Twin-Width Parameterized by the Feedback Edge Number Balabán, Jakub Ganian, Robert Rocton, Mathis twin-width parameterized complexity kernelization feedback edge number The problem of whether and how one can compute the twin-width of a graph - along with an accompanying contraction sequence - lies at the forefront of the area of algorithmic model theory. While significant effort has been aimed at obtaining a fixed-parameter approximation for the problem when parameterized by twin-width, here we approach the question from a different perspective and consider whether one can obtain (near-)optimal contraction sequences under a larger parameterization, notably the feedback edge number k. As our main contributions, under this parameterization we obtain (1) a linear bikernel for the problem of either computing a 2-contraction sequence or determining that none exists and (2) an approximate fixed-parameter algorithm which computes an 𝓁-contraction sequence (for an arbitrary specified 𝓁) or determines that the twin-width of the input graph is at least 𝓁. These algorithmic results rely on newly obtained insights into the structure of optimal contraction sequences, and as a byproduct of these we also slightly tighten the bound on the twin-width of graphs with small feedback edge number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Balabán and Robert Ganian and Mathis Rocton 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.7 urn:nbn:de:0030-drops-197170 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode