2026-08-17T09:52:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22229 2024-12-05T15:32:40Z ddc:004 open_access

Twin-Width Meets Feedback Edges and Vertex Integrity Balabán, Jakub Ganian, Robert Rocton, Mathis twin-width fixed-parameter algorithms feedback edge number vertex integrity 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: - An asymptotically tight bound between twin-width and the feedback edge number; - 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; - An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Balabán and Robert Ganian and Mathis Rocton 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.3 urn:nbn:de:0030-drops-222293 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.3 eng https://creativecommons.org/licenses/by/4.0/legalcode