A constant-factor approximation for weighted bond cover
Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos · Journal of Computer and System Sciences · 2025
The Weighted F - Vertex Deletion for a class F of graphs asks, weighted graph G , for a minimum weight vertex set S such that G − S ∈ F . The case when F is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted F - Vertex Deletion . Only three cases of minor-closed F are known to admit constant-factor approximations, namely Vertex Cover , Feedback Vertex Set and Diamond Hitting Set . We study the problem for the class F of θ c -minor-free graphs, under the equivalent setting of the Weighted c -Bond Cover problem, and present a constant-factor approximation algorithm using the primal-dual method. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted F - Vertex Deletion , our result may be useful as a template for algorithms for other minor-closed families.