Computing Twin-Width Parameterized by the Feedback Edge Number

D 2024

Computing Twin-Width Parameterized by the Feedback Edge Number

BALABÁN, Jakub; Robert GANIAN a Mathis ROCTON

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í

Dagstuhl, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), od s. "7:1"-"7:19", 19 s. 2024

Nakladatel

Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/24:00135638

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-311-9

ISSN

DOI

https://doi.org/10.4230/LIPIcs.STACS.2024.7

UT WoS

001300393400007

EID Scopus

2-s2.0-85187788952

Klíčová slova anglicky

twin-width; parameterized complexity; kernelization; feedback edge number

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 4. 4. 2025 11:14, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

MUNI/A/1592/2023, interní kód MU

Název: Modelování, analýza a verifikace (2024)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2024)

MUNI/A/1608/2023, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 24

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 24

Citovat

BALABÁN, Jakub; Robert GANIAN a Mathis ROCTON. Computing Twin-Width Parameterized by the Feedback Edge Number. Online. 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). Dagstuhl: Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik, 2024, s. "7:1"-"7:19", 19 s. ISBN 978-3-95977-311-9. Dostupné z: https://doi.org/10.4230/LIPIcs.STACS.2024.7.

@inproceedings{2382978,
   author = {Balabán, Jakub and Ganian, Robert and Rocton, Mathis},
   address = {Dagstuhl},
   booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
   doi = {https://doi.org/10.4230/LIPIcs.STACS.2024.7},
   editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
   keywords = {twin-width; parameterized complexity; kernelization; feedback edge number},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl},
   isbn = {978-3-95977-311-9},
   pages = {"7:1"-"7:19"},
   publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
   title = {Computing Twin-Width Parameterized by the Feedback Edge Number},
   url = {http://dx.doi.org/10.4230/LIPIcs.STACS.2024.7},
   year = {2024}
}

TY  - CONF
ID  - 2382978
AU  - Balabán, Jakub - Ganian, Robert - Rocton, Mathis
PY  - 2024
TI  - Computing Twin-Width Parameterized by the Feedback Edge Number
PB  - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
CY  - Dagstuhl
SN  - 9783959773119
KW  - twin-width
KW  - parameterized complexity
KW  - kernelization
KW  - feedback edge number
UR  - http://dx.doi.org/10.4230/LIPIcs.STACS.2024.7
N2  - 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.
ER  -

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

Přehled o publikaci