Publication details
Twin-Width Meets Feedback Edges and Vertex Integrity
| Authors | |
|---|---|
| Year of publication | 2024 |
| Type | Article in Proceedings |
| Conference | International Symposium on Parameterized and Exact Computation (IPEC) |
| MU Faculty or unit | |
| Citation | BALABÁN, Jakub, Robert GANIAN and Mathis ROCTON. Twin-Width Meets Feedback Edges and Vertex Integrity. Online. In {\'{E}}douard Bonnet and Pawel Rzazewski. International Symposium on Parameterized and Exact Computation (IPEC). 321st ed. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, 2024, p. "3:1"-"3:22", 22 pp. ISBN 978-3-95977-353-9. Available from: https://dx.doi.org/10.4230/LIPIcs.IPEC.2024.3. |
| web | https://doi.org/10.4230/LIPIcs.IPEC.2024.3 |
| Doi | http://dx.doi.org/10.4230/LIPIcs.IPEC.2024.3 |
| 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: |