arxiv: 2605.07941 · v1 · submitted 2026-05-08 · 💻 cs.DS · cs.DM

Recognition: no theorem link

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

Christian Komusiewicz , Nils Morawietz

Authors on Pith no claims yet

Pith reviewed 2026-05-11 03:04 UTC · model grok-4.3

classification 💻 cs.DS cs.DM

keywords vertex coverlocal searchk-swaph-indextreewidthmodular-widthparameterized algorithmmodular decomposition

0 comments

The pith

Local search for vertex covers admits algorithms with running time ℓ to the power of a function of k times n to a constant, when ℓ is the h-index, treewidth, or modular-width.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper focuses on the local-search variant of vertex cover in which a given cover S is improved by swapping a set W of size at most k if the symmetric difference yields a smaller cover. Because k is treated as a user-chosen constant that trades speed against solution quality, the goal is algorithms whose running time is polynomial in n yet only mildly exponential in a structural parameter ℓ of the input graph. Such algorithms are obtained when ℓ is the h-index, the treewidth, or the modular-width; a new parameter measuring the maximum degree of quotient graphs in a modular decomposition is introduced and handled similarly. The same approach extends to the weighted setting in which one seeks a k-swap that decreases the total weight by at least d. A reader would care because this decouples the cost of local improvement from the raw size n, making repeated local search practical on large graphs that nevertheless possess small structural measures.

Core claim

For the decision problem LS Vertex Cover—given a vertex cover S and integer k, decide whether a valid improving k-swap exists—we obtain algorithms running in time ℓ^{f(k)} n^{O(1)} whenever ℓ is the h-index, treewidth or modular-width of G. We also introduce the parameter that is the maximum degree taken over all quotient graphs appearing in a modular decomposition of G and give an algorithm with the same form of running time for it. The results carry over to the weighted generalization in which one asks for a valid k-swap that improves the cover weight by at least d.

What carries the argument

Parameterized enumeration or verification of candidate k-swaps, bounded via dynamic programming or bounded-height search trees on tree decompositions, modular decompositions, or degree-bounded h-index subgraphs.

If this is right

Repeated local-search steps can improve vertex-cover solutions on graphs of small treewidth without fixing the global solution size as a parameter.
The modular-decomposition degree parameter captures additional graph classes whose treewidth or h-index may be large yet whose quotient degrees remain small.
A user can increase the swap radius k to obtain better covers while the running time remains polynomial in n for any fixed structural ℓ.
The weighted d-improving variant inherits the same mild dependence on ℓ, enabling local search on weighted instances with the same structural guarantees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same decomposition techniques could be adapted to local-search neighborhoods of other covering problems such as dominating set.
Preprocessing routines that reduce the structural parameter before local search begins would compose naturally with these algorithms.
Empirical evaluation on graphs whose h-index or modular-width is known to be small would test whether the theoretical bounds produce observable speed-ups in practice.

Load-bearing premise

The chosen structural parameter ℓ must be small enough that raising it to a power depending only on the fixed constant k still produces acceptable running time.

What would settle it

A concrete infinite family of graphs with h-index bounded by 5 on which every algorithm that correctly decides the existence of an improving 3-swap requires time superpolynomial in the h-index.

read the original abstract

A vertex set $W$ in a graph $G$ is a valid $k$-swap for a vertex cover $S$ of $G$ if $W$ has size at most $k$ and $S'=(S \setminus W) \cup (W \setminus 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 a valid 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 $\ell^{f(k)}\cdot n^{\mathcal{O}(1)}$ where $\ell$ is a structural graph parameter upper-bounded by $n$. We say that such a running time grows mildly with respect to $\ell$ and strongly with respect to $k$. We obtain algorithms with such a running time for $\ell$ 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 valid $d$-improving $k$-swap, that is, a valid $k$-swap which decreases the weight of the vertex cover by at least $d$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives FPT algorithms for local search vertex cover that run in ℓ^{f(k)} n^{O(1)} time when ℓ is the h-index, treewidth, modular-width, or a new modular-decomposition degree parameter.

read the letter

The main point is that this paper gives FPT algorithms for local search vertex cover with running times of the form ℓ^{f(k)} n^{O(1)}, where ℓ is one of several structural parameters and k is treated as a constant. This is useful because the problem is W[1]-hard in k alone. They handle the h-index, treewidth, and modular-width. They also define a new parameter as the max degree in the quotient graphs from a modular decomposition. The algorithms are adapted to the weighted d-improving version as well. What the paper does well is to take the standard local search setup and show how to exploit these parameters to enumerate or DP over possible swaps without blowing up the time too much in n. The motivation from applications where k is small is reasonable, and the extension to weights is a natural addition. The soft spots are not major. The new parameter is a bit specialized, so its impact might be limited to certain graph classes. The dependence on k in the exponent is not specified in detail here, but as long as it's computable it's fine for small k. The abstract claims the running times exist, and the strategy seems consistent with known methods for these parameters. This paper is for people in the parameterized algorithms community who focus on graph problems like vertex cover and local search. A reader interested in structural parameters and how they can make heuristics faster would find it worthwhile. It deserves a serious referee because the claims are new and the approach is sound on the surface. I would send it for peer review.

Referee Report

0 major / 3 minor

Summary. The paper studies the Local Search Vertex Cover problem: given a vertex cover S of G, decide if there exists a valid improving k-swap W (|W|≤k) such that the symmetric difference S Δ W is a smaller vertex cover. Motivated by W[1]-hardness parameterized by k (with k treated as a small user constant), the authors design algorithms running in ℓ^{f(k)} n^{O(1)} time for structural parameters ℓ, specifically the h-index, treewidth, modular-width, and a novel parameter (maximum degree over quotient graphs in a modular decomposition of G). The results are extended to the weighted setting seeking d-improving k-swaps.

Significance. If the claimed running times hold, the work supplies a useful bridge between local-search heuristics and parameterized algorithms by showing that structural parameters suffice to keep the dependence on the search radius k mild (exponential only in f(k)). The explicit treatment of four different parameters, the introduction of the modular-decomposition degree parameter, and the adaptation to weighted d-improving swaps are concrete strengths. The approach relies on standard FPT techniques (enumeration and DP) adapted to the swap-verification setting and appears free of hidden n-factors in the exponent.

minor comments (3)

The definition of the novel parameter (maximum degree over all quotient graphs in a modular decomposition) is introduced in the abstract but should receive an explicit formal definition, notation, and a short example in the preliminaries section to avoid ambiguity when implementing the corresponding algorithm.
For each of the four parameters, the manuscript should state an explicit upper bound on the function f(k) (or at least the degree of the polynomial in ℓ) rather than leaving it as an unspecified f(k); this would make the running-time claims immediately verifiable from the text.
A small illustrative example (a graph, a vertex cover S, and a concrete improving 2-swap) placed early in the introduction would help readers unfamiliar with the local-search formulation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work, for highlighting its strengths in connecting local-search heuristics with parameterized algorithms, and for recommending minor revision. No specific major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper constructs explicit algorithms for LS Vertex Cover (and its weighted variant) that run in ℓ^{f(k)} n^{O(1)} time when ℓ is the h-index, treewidth, modular-width, or the maximum degree in modular-decomposition quotient graphs. These running times are obtained via standard enumeration and dynamic programming over the structural parameter ℓ while treating k as a fixed constant; the constructions rely on graph-theoretic properties of the chosen parameters and do not reduce the claimed time bounds to any fitted quantity, self-defined relation, or load-bearing self-citation. The W[1]-hardness result for parameter k is invoked only as motivation and is independent of the new algorithms.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on standard graph-theoretic definitions and the existence of dynamic-programming or branching routines on graphs of bounded treewidth or modular-width; one new parameter is introduced without external validation.

axioms (1)

standard math Standard definitions of vertex cover, symmetric difference, and W[1]-hardness of LS Vertex Cover parameterized by k alone.
Invoked in the motivation and problem statement.

invented entities (1)

maximum degree over all quotient graphs in a modular decomposition no independent evidence
purpose: Novel structural parameter that yields the desired running-time bound.
Introduced in the abstract as an additional parameter for which the algorithm works.

pith-pipeline@v0.9.0 · 5662 in / 1358 out tokens · 33834 ms · 2026-05-11T03:04:37.486587+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

149 extracted references · 149 canonical work pages · 1 internal anchor

[1]

2025 , url_ =

Niels Gr. 2025 , url_ =

work page 2025
[2]

Graph clustering problems under the lens of parameterized local search , journal =

Jaroslav Garvardt and Nils Morawietz and Andr. Graph clustering problems under the lens of parameterized local search , journal =. 2026 , url =. doi:10.1016/J.JCSS.2026.103784 , timestamp =

work page doi:10.1016/j.jcss.2026.103784 2026
[3]

Amir Abboud and Arturs Backurs and Virginia Vassilevska Williams , editor_ =

work page
[4]

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser , journal =

Amir Abboud and Arturs Backurs and Virginia Vassilevska Williams , title =. doi:10.1137/16M1061771 , timestamp =

work page doi:10.1137/16m1061771
[5]

Manuel Aprile and Matthew Drescher and Samuel Fiorini and Tony Huynh , title =

work page
[6]

Rao , editor_ =

David Arbour and Drew Dimmery and Anup B. Rao , editor_ =

work page
[7]

Andreatta and Celso C

Alexandre A. Andreatta and Celso C. Ribeiro , title =

work page
[8]

Balanced graph partitioning,

Konstantin Andreev and Harald R. 2006 , url_ =. doi:10.1007/S00224-006-1350-7 , timestamp_ =

work page doi:10.1007/s00224-006-1350-7 2006
[9]

Diogo Vieira Andrade and Mauricio G. C. Resende and Renato Fonseca F. Werneck , title =

work page
[10]

and Steel, Mike , title =

Allen, Benjamin L. and Steel, Mike , title =

work page
[11]

A Refined Laser Method and Faster Matrix Multiplication , booktitle =

Josh Alman and Virginia Vassilevska Williams , editor__ =. doi:10.1137/1.9781611976465.32 , timestamp =

work page doi:10.1137/1.9781611976465.32
[12]

Color-coding , Url =

Noga Alon and Raphael Yuster and Uri Zwick , title =. 1995 , url_ =. doi:10.1145/210332.210337 , timestamp_ =

work page doi:10.1145/210332.210337 1995
[13]

Bodlaender , title =

Hans L. Bodlaender , title =. doi:10.1137/S0097539793251219 , timestamp =

work page doi:10.1137/s0097539793251219
[14]

Nikhil Bansal and Avrim Blum and Shuchi Chawla , title =

work page
[15]

Bodlaender and Rodney G

Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Danny Hermelin , title =

work page
[16]

2008 , url_ =

Ulrik Brandes and Daniel Delling and Marco Gaertler and Robert G. 2008 , url_ =. doi:10.1109/TKDE.2007.190689 , timestamp_ =

work page doi:10.1109/tkde.2007.190689 2008
[17]

2015 , url_ =

Flavia Bonomo and Guillermo Dur. 2015 , url_ =. doi:10.1016/J.TCS.2015.07.001 , timestamp_ =

work page doi:10.1016/j.tcs.2015.07.001 2015
[18]

Bodlaender and Michael R

Hans L. Bodlaender and Michael R. Fellows and Tandy J. Warnow , editor__ =

work page
[19]

Bodlaender and Bart M

Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch , title =

work page
[20]

Piotr Berman and Marek Karpinski , editor__ =

work page
[21]

Mark de Berg and Bart M. P. Jansen and Debankur Mukherjee , title =

work page
[22]

Berend, Daniel and Tassa, Tamir , title =

work page
[23]

Kearney and Ming Li , editor_ =

David Bryant and John Tsang and Paul E. Kearney and Ming Li , editor_ =. 2000 , url_ =

work page 2000
[24]

Juedes and Iyad A

Jianer Chen and Benny Chor and Mike Fellows and Xiuzhen Huang and David W. Juedes and Iyad A. Kanj and Ge Xia , title =

work page
[25]

Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. doi:10.1007/978-3-319-21275-3 , isbn =

work page doi:10.1007/978-3-319-21275-3
[26]

and Edwards, Anthony W

Cavalli-Sforza, Luigi L. and Edwards, Anthony W. F. , title =

work page
[27]

Cao, Yixin and Chen, Jianer , title =

work page
[28]

Katrin Casel and Henning Fernau and Mehdi

work page
[29]

Jianer Chen and Jie Meng , title =

work page
[30]

Vaggos Chatziafratis and Mohammad Mahdian and Sara Ahmadian , editor__ =

work page
[31]

Shuchi Chawla and Konstantin Makarychev and Tselil Schramm and Grigory Yaroslavtsev , title =

work page
[32]

Amir Carmel and Noa Musa

work page
[33]

Shaowei Cai and Kaile Su and Chuan Luo and Abdul Sattar , title =

work page
[34]

Yixin Cao and Yuping Ke , editor__ =

work page
[35]

doi:10.1006/jagm.2000.1090 , timestamp =

Elias Dahlhaus , title =. doi:10.1006/jagm.2000.1090 , timestamp =

work page doi:10.1006/jagm.2000.1090 2000
[36]

Dailey , title =

David P. Dailey , title =

work page
[37]

Valentin Bartier and Gabriel Bathie and Nicolas Bousquet and Marc Heinrich and Th

work page
[38]

Martin Josef Geiger , title =

work page
[39]

Sylwester Swat , title =

work page
[40]

Downey and Michael R

Rodney G. Downey and Michael R. Fellows , title =

work page
[41]

Goldberg and Alexander Noe and Nikos Parotsidis and Mauricio G

Yuanyuan Dong and Andrew V. Goldberg and Alexander Noe and Nikos Parotsidis and Mauricio G. C. Resende and Quico Spaen , editor__ =

work page
[42]

1973 , publisher=

Duda, Richard O and Hart, Peter E and Stork, David G , volume_=. 1973 , publisher=

work page 1973
[43]

Werneck , editor__ =

Jakob Dahlum and Sebastian Lamm and Peter Sanders and Christian Schulz and Darren Strash and Renato F. Werneck , editor__ =

work page
[44]

Alexander Dobler and Manuel Sorge and Ana

work page
[45]

Michael Etscheid and Stefan Kratsch and Matthias Mnich and Heiko R

work page
[46]

and McMorris, F

Estabrook, George F. and McMorris, F. R. and Meacham, Christopher A. , journal =. 1985 , month_ =. doi:10.2307/sysbio/34.2.193 , url_ =

work page doi:10.2307/sysbio/34.2.193 1985
[47]

Spiro , title =

David Eppstein and Emma S. Spiro , title =

work page
[48]

Felsenstein, Joseph , title=

work page
[49]

Fellows and Fedor V

Michael R. Fellows and Fedor V. Fomin and Daniel Lokshtanov and Frances A. Rosamond and Saket Saurabh and Yngve Villanger , title =

work page
[50]

, title=

Fitch, Walter M. , title=

work page
[51]

Frieze and Mark Jerrum , title =

Alan M. Frieze and Mark Jerrum , title =

work page
[52]

Pedro Felzenszwalb and Caroline Klivans and Alice Paul , title =

work page
[53]

Fellows and Michael A

Michael R. Fellows and Michael A. Langston and Frances A. Rosamond and Peter Shaw , title =

work page
[54]

Fomin and Daniel Lokshtanov and Venkatesh Raman and Saket Saurabh , editor_ =

Fedor V. Fomin and Daniel Lokshtanov and Venkatesh Raman and Saket Saurabh , editor_ =

work page
[55]

Fomin and Daniel Lokshtanov and Saket Saurabh and Michal Pilipczuk and Marcin Wrochna , title =

Fedor V. Fomin and Daniel Lokshtanov and Saket Saurabh and Michal Pilipczuk and Marcin Wrochna , title =. doi:10.1145/3186898 , timestamp =

work page doi:10.1145/3186898
[56]

and Graham, Ronald L

Foulds, Les R. and Graham, Ronald L. , title =

work page
[57]

Pardalos and Mauricio G

Paola Festa and Panos M. Pardalos and Mauricio G. C. Resende and Celso C. Ribeiro , title =

work page
[58]

2004 , url_ =

Ganapathy, Ganeshkumar and Ramachandran, Vijaya and Warnow, Tandy , title =. 2004 , url_ =

work page 2004
[59]

Jens Gramm and Jiong Guo and Falk H

work page
[60]

2008 , url_ =

Jens Gramm and Arfst Nickelsen and Till Tantau , title =. 2008 , url_ =. doi:10.1093/COMJNL/BXM049 , timestamp_ =

work page doi:10.1093/comjnl/bxm049 2008
[61]

doi:10.1007/s00453-018-0499-1 , timestamp =

Serge Gaspers and Joachim Gudmundsson and Mitchell Jones and Juli. doi:10.1007/s00453-018-0499-1 , timestamp =

work page doi:10.1007/s00453-018-0499-1
[62]

doi:10.24963/ijcai.2023/620 , timestamp =

Jaroslav Garvardt and Niels Gr. doi:10.24963/ijcai.2023/620 , timestamp =

work page doi:10.24963/ijcai.2023/620 2023
[63]

Jiong Guo and Danny Hermelin and Christian Komusiewicz , title =

work page
[64]

Jiong Guo and Sepp Hartung and Rolf Niedermeier and Ondrej Such

work page
[65]

M. R. Garey and David S. Johnson , title =

work page
[66]

M. R. Garey and David S. Johnson and Robert Endre Tarjan , title =

work page
[67]

Daya Ram Gaur and Ramesh Krishnamurti and Rajeev Kohli , title =

work page
[68]

Serge Gaspers and Eun Jung Kim and Sebastian Ordyniak and Saket Saurabh and Stefan Szeider , editor__ =

work page
[69]

Goloboff , title =

Pablo A. Goloboff , title =. doi:https://doi.org/10.1006/clad.1999.0122 , url_ =

work page doi:10.1006/clad.1999.0122 1999
[70]

Goloboff, Pablo A , title =

work page
[71]

Warnow , editor__ =

Ganeshkumar Ganapathy and Vijaya Ramachandran and Tandy J. Warnow , editor__ =

work page
[72]

Jana Holznigenkemper and Christian Komusiewicz and Nils Morawietz and Bernhard Seeger , editor__ =

work page
[73]

Weiran Huang and Liang Li and Wei Chen , editor__ =

work page
[74]

Hallett and Catherine McCartin , title =

Michael T. Hallett and Catherine McCartin , title =. Theory of Computing Systems , volume =. 2007 , url_ =. doi:10.1007/S00224-007-1329-Z , timestamp_ =

work page doi:10.1007/s00224-007-1329-z 2007
[75]

Sepp Hartung and Rolf Niedermeier , title =

work page
[76]

Hoos and Thomas St

Holger H. Hoos and Thomas St

work page
[77]

and Wu, Taoyang , title=

Humphries, Peter J. and Wu, Taoyang , title=

work page
[78]

Iersel, Leo Van and Jones, Mark and Kelk, Steven , title =

work page
[79]

Italiano and Athanasios L

Giuseppe F. Italiano and Athanasios L. Konstantinidis and Charis Papadopoulos , editor_ =

work page
[80]

Russell Impagliazzo and Ramamohan Paturi and Francis Zane , title =

work page

Showing first 80 references.