Eun Jung Kim (김은정), A Constant-factor Approximation for Weighted Bond Cover

The Weighted $\mathcal{F}$-Vertex Deletion for a class $\mathcal{F}$ of graphs asks, given a weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in \mathcal{F}$. The case when $\mathcal{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 $\mathcal{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 $\mathcal{F}$ of ${\theta }_c$-minor-free graphs, under the equivalent setting of the Weighted c-Bond Cover, 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 ${\theta }_c$-minor-model either contains a large two-terminal protrusion, or contains a constant-size ${\theta }_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.

This is joint work with Euiwoong Lee and Dimitrios M. Thilikos.