Twin-Width Meets Feedback Edges and Vertex Integrity

D 2024

Twin-Width Meets Feedback Edges and Vertex Integrity

BALABÁN, Jakub; Robert GANIAN a Mathis ROCTON

Základní údaje

Originální název

Twin-Width Meets Feedback Edges and Vertex Integrity

Autoři

BALABÁN, Jakub; Robert GANIAN a Mathis ROCTON

Vydání

321. vyd. Dagstuhl, International Symposium on Parameterized and Exact Computation (IPEC), od s. "3:1"-"3:22", 22 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:00136984

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-353-9

ISSN

DOI

https://doi.org/10.4230/LIPIcs.IPEC.2024.3

EID Scopus

2-s2.0-85213377881

Klíčová slova anglicky

twin-width; fixed-parameter algorithms; feedback edge number; vertex integrity

Štítky

core_B, firank_B

Příznaky

Mezinárodní význam, Recenzováno

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

Anotace

V originále

The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider the approximability of twin-width via fixed-parameter algorithms whose running time depends not on twin-width itself, but rather on parameters which impose stronger restrictions on the input graph. The first step that article made in this direction is to establish the fixed-parameter approximability of twin-width (with an additive error of 1) when the runtime parameter is the feedback edge number. Here, we make several new steps in this research direction and obtain: (1) An asymptotically tight bound between twin-width and the feedback edge number; (2) A significantly improved fixed-parameter approximation algorithm for twin-width under the same runtime parameter (i.e., the feedback edge number) which circumvents many of the technicalities of the original result and simultaneously avoids its formerly non-elementary runtime dependency; and (3) An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph.

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)

Citovat

BALABÁN, Jakub; Robert GANIAN a Mathis ROCTON. Twin-Width Meets Feedback Edges and Vertex Integrity. Online. In {\'{E}}douard Bonnet and Pawel Rzazewski. International Symposium on Parameterized and Exact Computation (IPEC). 321. vyd. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, 2024, s. "3:1"-"3:22", 22 s. ISBN 978-3-95977-353-9. Dostupné z: https://doi.org/10.4230/LIPIcs.IPEC.2024.3.

@inproceedings{2427437,
   author = {Balabán, Jakub and Ganian, Robert and Rocton, Mathis},
   address = {Dagstuhl},
   booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)},
   doi = {https://doi.org/10.4230/LIPIcs.IPEC.2024.3},
   edition = {321},
   editor = {{\'{E}}douard Bonnet and Pawel Rzazewski},
   keywords = {twin-width; fixed-parameter algorithms; feedback edge number; vertex integrity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl},
   isbn = {978-3-95977-353-9},
   pages = {"3:1"-"3:22"},
   publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
   title = {Twin-Width Meets Feedback Edges and Vertex Integrity},
   url = {https://doi.org/10.4230/LIPIcs.IPEC.2024.3},
   year = {2024}
}

TY  - CONF
ID  - 2427437
AU  - Balabán, Jakub - Ganian, Robert - Rocton, Mathis
PY  - 2024
TI  - Twin-Width Meets Feedback Edges and Vertex Integrity
PB  - Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik
CY  - Dagstuhl
SN  - 9783959773539
KW  - twin-width
KW  - fixed-parameter algorithms
KW  - feedback edge number
KW  - vertex integrity
UR  - https://doi.org/10.4230/LIPIcs.IPEC.2024.3
N2  - The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider the approximability of twin-width via fixed-parameter algorithms whose running time depends not on twin-width itself, but rather on parameters which impose stronger restrictions on the input graph. The first step that article made in this direction is to establish the fixed-parameter approximability of twin-width (with an additive error of 1) when the runtime parameter is the feedback edge number. Here, we make several new steps in this research direction and obtain: (1) An asymptotically tight bound between twin-width and the feedback edge number; (2) A significantly improved fixed-parameter approximation algorithm for twin-width under the same runtime parameter (i.e., the feedback edge number) which circumvents many of the technicalities of the original result and simultaneously avoids its formerly non-elementary runtime dependency; and (3) An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph.
ER  -

BALABÁN, Jakub; Robert GANIAN a Mathis ROCTON. Twin-Width Meets Feedback Edges and Vertex Integrity. Online. In $\{\backslash$'$\{$E$\}\}$douard Bonnet and Pawel Rzazewski. \textit{International Symposium on Parameterized and Exact Computation (IPEC)}. 321. vyd. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum f$\{\backslash$''$\{$u$\}\}$r Informatik, 2024, s.~''3:1''-''3:22'', 22 s. ISBN~978-3-95977-353-9. Dostupné z: https://doi.org/10.4230/LIPIcs.IPEC.2024.3.

Přehled o publikaci