A constant-factor approximation for weighted bond cover

Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021
EditorsMary Wootters, Laura Sanita
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772075
DOIs
StatePublished - Sep 1 2021
Event24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 - Virtual, Seattle, United States
Duration: Aug 16 2021Aug 18 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume207
ISSN (Print)1868-8969

Conference

Conference24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021
Country/TerritoryUnited States
CityVirtual, Seattle
Period8/16/218/18/21

Keywords

  • Bonds in graphs
  • Constant-factor approximation algorithms
  • Graph minors
  • Graph modification problems
  • Primal-dual method

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'A constant-factor approximation for weighted bond cover'. Together they form a unique fingerprint.

Cite this