Abstract
The Weighted ℱVertex Deletion for a class ℱ of graphs asks, weighted graph G, for a minimum weight vertex set S such that GS ∈ ℱ. The case when ℱ is minorclosed and excludes some graph as a minor has received particular attention but a constantfactor approximation remained elusive for Weighted ℱVertex Deletion. Only three cases of minorclosed ℱ are known to admit constantfactor approximations, namely Vertex Cover, Feedback Vertex Set and Diamond Hitting Set. We study the problem for the class ℱ of θ_cminorfree graphs, under the equivalent setting of the Weighted cBond Cover problem, and present a constantfactor approximation algorithm using the primaldual method. For this, we leverage a structure theorem implicit in [Joret et al., SIDMA'14] which states the following: any graph G containing a θ_cminormodel either contains a large twoterminal protrusion, or contains a constantsize θ_cminormodel, or a collection of pairwise disjoint constantsized 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 specialpurpose 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 constantfactor approximation for Weighted ℱVertex Deletion, our result may be useful as a template for algorithms for other minorclosed families.
BibTeX  Entry
@InProceedings{kim_et_al:LIPIcs.APPROX/RANDOM.2021.7,
author = {Kim, Eun Jung and Lee, Euiwoong and Thilikos, Dimitrios M.},
title = {{A ConstantFactor Approximation for Weighted Bond Cover}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {7:17:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14700},
URN = {urn:nbn:de:0030drops147002},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.7},
annote = {Keywords: Constantfactor approximation algorithms, Primaldual method, Bonds in graphs, Graph minors, Graph modification problems}
}
Keywords: 

Constantfactor approximation algorithms, Primaldual method, Bonds in graphs, Graph minors, Graph modification problems 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) 
Issue Date: 

2021 
Date of publication: 

15.09.2021 