Computing Twin-Width Parameterized by the Feedback Edge Number and Vertex Integrity
| Autoři | |
|---|---|
| Rok publikování | 2025 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | SIAM JOURNAL ON DISCRETE MATHEMATICS |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://doi.org/10.1137/24m1705329 |
| Doi | https://doi.org/10.1137/24M1705329 |
| Klíčová slova | twin-width; parameterized complexity; kernelization; feedback edge number |
| Popis | 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 larger runtime parameters. As our main contributions, we obtain fixed-parameter approximation algorithms for twin-width when the runtime parameter is either the vertex integrity or the feedback edge number of the input graph. For the latter parameter, we also obtain a linear kernel for the problem of either computing a 2-contraction sequence or determining that none exists. For both parameters, we also obtain asymptotically tight upper bounds on twin-width. |
| Související projekty: |