2026-07-23T16:05:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17376 2024-03-06T10:59:35Z ddc:004 open_access

Parameterized Local Search for Vertex Cover: When Only the Search Radius Is Crucial Komusiewicz, Christian Morawietz, Nils Local Search Structural parameterization Fixed-parameter tractability A k-swap W for a vertex cover S of a graph G is a vertex set of size at most k such that S' = (S ⧵ W) ∪ (W ⧵ S), the symmetric difference of S and W, is a vertex cover of G. If |S'| < |S|, then W is improving. In LS-Vertex Cover, one is given a vertex cover S of a graph G and wants to know if there is an improving k-swap for S in G. In applications of LS-Vertex Cover, k is a very small parameter that can be set by a user to determine the trade-off between running time and solution quality. Consequently, k can be considered to be a constant. Motivated by this and the fact that LS-Vertex Cover is W[1]-hard with respect to k, we aim for algorithms with running time 𝓁^f(k) ⋅ n^𝒪(1) where 𝓁 is a structural graph parameter upper-bounded by n. We say that such a running time grows mildly with respect to 𝓁 and strongly with respect to k. We obtain algorithms with such a running time for 𝓁 being the h-index of G, the treewidth of G, or the modular-width of G. In addition, we consider a novel parameter, the maximum degree over all quotient graphs in a modular decomposition of G. Moreover, we adapt these algorithms to the more general problem where each vertex is assigned a weight and where we want to find a d-improving k-swap, that is, a k-swap which decreases the weight of the vertex cover by at least d. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Komusiewicz and Nils Morawietz 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.20 urn:nbn:de:0030-drops-173764 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.20 eng https://creativecommons.org/licenses/by/4.0/legalcode