Computing Twin-Width Parameterized by the Feedback Edge Number

BALABÁN, Jakub, Robert GANIAN a Mathis ROCTON. Computing Twin-Width Parameterized by the Feedback Edge Number. In Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel. 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik, 2024, s. 7:1--7:19. ISBN 978-3-95977-311-9. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.STACS.2024.7.

Základní údaje

• Originální název: Computing Twin-Width Parameterized by the Feedback Edge Number
• Autoři: BALABÁN, Jakub, Robert GANIAN a Mathis ROCTON.
• Vydání: 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), od s. 7:1--7:19, 2024.
• Nakladatel: Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik

Další údaje

• Typ výsledku: Stať ve sborníku
• Utajení: není předmětem státního či obchodního tajemství
• ISBN: 978-3-95977-311-9
• Doi: http://dx.doi.org/10.4230/LIPIcs.STACS.2024.7
• Klíčová slova anglicky: twin-width, parameterized complexity, kernelization, feedback edge number
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.