Twin-Width Meets Feedback Edges and Vertex Integrity

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BALABÁN Jakub GANIAN Robert ROCTON Mathis

Year of publication 2024
Type Article in Proceedings
Conference International Symposium on Parameterized and Exact Computation (IPEC)
MU Faculty or unit

Faculty of Informatics

Citation
Keywords twin-width; fixed-parameter algorithms; feedback edge number; vertex integrity
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.