Abstract
The WFD for a class $F$ of graphs asks, weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in 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 WFD. Only three cases of minor-closed $F$ are known to admit constant-factor approximations, namely $\text{Vertex Cover}$, $\text{Feedback Vertex Set}$ and $\text{Diamond Hitting Set}$. We study the problem for the class $F$ of $\theta_c$-minor-free graphs, under the equivalent setting of the $pumpkin$ problem, and present a constant-factor approximation algorithm using the primal-dual method. For this, we leveragea structure theorem implicit in [Joret, Paul, Sau, Saurabh, and Thomassé, 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 WFD, our result may be useful as a template for algorithms for other minor-closed families.