Computing Twin-Width Parameterized by the Feedback Edge Number
| Authors | |
|---|---|
| Year of publication | 2024 |
| Type | Article in Proceedings |
| Conference | 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.STACS.2024.7 |
| Keywords | twin-width, parameterized complexity, kernelization, feedback edge number |
| Description | 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. |
| Related projects: |