A Constant-factor Approximation for Weighted Bond Cover
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929665423179776 |
|---|---|
| author | Kim, Eun Jung Lee, Euiwoong Thilikos, Dimitrios M. |
| author_facet | Kim, Eun Jung Lee, Euiwoong Thilikos, Dimitrios M. |
| contents | The Weighted $\mathcal{F}$-Vertex Deletion for a class ${\cal F}$ of graphs asks, weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in{\cal F}.$ The case when ${\cal F}$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal{F}$-Vertex Deletion. Only three cases of minor-closed ${\cal 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 ${\cal 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, Paul, Sau, Saurabh, and Thomassé, 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 $\mathcal{F}$-Vertex Deletion, our result may be useful as a template for algorithms for other minor-closed families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_00857 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Constant-factor Approximation for Weighted Bond Cover Kim, Eun Jung Lee, Euiwoong Thilikos, Dimitrios M. Data Structures and Algorithms 05C35, 05C83, 05C85, 68R10, 68W25 F.2.2; G.2.2 The Weighted $\mathcal{F}$-Vertex Deletion for a class ${\cal F}$ of graphs asks, weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in{\cal F}.$ The case when ${\cal F}$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal{F}$-Vertex Deletion. Only three cases of minor-closed ${\cal 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 ${\cal 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, Paul, Sau, Saurabh, and Thomassé, 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 $\mathcal{F}$-Vertex Deletion, our result may be useful as a template for algorithms for other minor-closed families. |
| title | A Constant-factor Approximation for Weighted Bond Cover |
| topic | Data Structures and Algorithms 05C35, 05C83, 05C85, 68R10, 68W25 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2105.00857 |