Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial

Christian Komusiewicz, Nils Morawietz · 2026

Read Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial by Christian Komusiewicz, Nils Morawietz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07941.txt.

Description

Christian Komusiewicz and Nils Morawietz analyze a local search problem for vertex covers, sets of vertices that touch every edge of a graph. A swap exchanges a few vertices of the cover for others; if the new cover is smaller, the swap improves the solution. Users keep the swap size small to balance speed and quality.

Because the problem is hard when measured by swap size alone, the authors seek running times that grow mildly in a structural graph parameter and strongly only in the swap size. They obtain such algorithms when the parameter is the h-index or the treewidth of the graph, giving practical routes for structured instances.

Catalog record

CREATORChristian Komusiewicz, Nils Morawietz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.07941

Browse the full library · About the Tower of Babel