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
| CREATOR | Christian Komusiewicz, Nils Morawietz |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 147 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.07941