A Constant-Factor Approximation for Weighted Bond Cover
Kim, Eun Jung; Lee, Euiwoong; Thilikos, Dimitrios M. (2021), A Constant-Factor Approximation for Weighted Bond Cover, in Wootters, Mary; Sanità, Laura, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, p. 7:1--7:14. 10.4230/LIPIcs.APPROX/RANDOM.2021.7
TypeCommunication / Conférence
Book titleApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021
Book authorWootters, Mary; Sanità, Laura
MetadataShow full item record
Author(s)Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Thilikos, Dimitrios M.
Abstract (EN)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. 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 F-Vertex Deletion, our result may be useful as a template for algorithms for other minor-closed families.
Subjects / KeywordsGraph minors; Graph modification problems; Bonds in graphs; Primal-dual method; Constant-factor approximation algorithms
Showing items related by title and author.
Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié