2026-07-23T15:19:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14700 2024-03-06T10:54:41Z ddc:004 open_access

A Constant-Factor Approximation for Weighted Bond Cover Kim, Eun Jung Lee, Euiwoong Thilikos, Dimitrios M. Constant-factor approximation algorithms Primal-dual method Bonds in graphs Graph minors Graph modification problems The Weighted ℱ-Vertex Deletion for a class ℱ of graphs asks, weighted graph G, for a minimum weight vertex set S such that G-S ∈ ℱ. The case when ℱ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted ℱ-Vertex Deletion. Only three cases of minor-closed ℱ are known to admit constant-factor approximations, namely Vertex Cover, Feedback Vertex Set and Diamond Hitting Set. We study the problem for the class ℱ 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. For this, we leverage a structure theorem implicit in [Joret et al., SIDMA'14] which states the following: any graph G containing a θ_c-minor-model either contains a large two-terminal protrusion, or contains a constant-size θ_c-minor-model, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted ℱ-Vertex Deletion, our result may be useful as a template for algorithms for other minor-closed families. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eun Jung Kim and Euiwoong Lee and Dimitrios M. Thilikos 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.7 urn:nbn:de:0030-drops-147002 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode