Publication details
Computing Twin-Width Parameterized by the Feedback Edge Number and Vertex Integrity
| Authors | |
|---|---|
| Year of publication | 2025 |
| Type | Article in Periodical |
| Magazine / Source | SIAM JOURNAL ON DISCRETE MATHEMATICS |
| MU Faculty or unit | |
| Citation | |
| web | https://doi.org/10.1137/24m1705329 |
| Doi | https://doi.org/10.1137/24M1705329 |
| 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 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. |
| Related projects: |