Computing Twin-Width Parameterized by the Feedback Edge Number
| Autoři | |
|---|---|
| Rok publikování | 2024 |
| Druh | Článek ve sborníku |
| Konference | 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.STACS.2024.7 |
| 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 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. |
| Související projekty: |