An $O(\log OPT)$-approximation for covering and packing minor models of ${\theta }_r$

Abstract

Given two graphs $G$ and $H$, we define ${\text{v-cover}}_H(G)$ (resp. ${\text{e-cover}}_H(G)$) as the minimum number of vertices (resp. edges) whose removal from $G$ produces a graph without any minor isomorphic to $H$. Also ${\text{v-pack}}_H(G)$ (resp. ${\text{v-pack}}_H(G)$) is the maximum number of vertex- (resp. edge-) disjoint subgraphs of $G$ that contain a minor isomaorphic to $H$. We denote by ${\theta }_r$ the graph with two vertices and $r$ parallel edges between them. When $H={\theta }_r$, the parameters ${\text{v-cover}}_H$, ${\text{e-cover}}_H$, ${\text{v-pack}}_H$, and ${\text{v-pack}}_H$ are NP-hard to compute (for sufficiently big values of $r$). Drawing upon combinatorial results in [Minors in graphs of large ${\theta }_r$-girth, Chatzidimitriou et al., arXiv:1510.03041], we give an algorithmic proof that if ${\text{v-pack}}_{{\theta }_r}(G)\le k$, then ${\text{v-cover}}_{{\theta }_r}(G)=O(k\log k)$, and similarly for ${\text{v-pack}}_{{\theta }_r}$ and ${\text{e-cover}}_{{\theta }_r}$. In other words, the class of graphs containing ${\theta }_r$ as a minor has the vertex/edge Erdős-Pósa property, for every positive integer $r$. Using the algorithmic machinery of our proofs, we introduce a unified approach for the design of an $O(\log \mathrm{OPT})$-approximation algorithm for ${\text{v-pack}}_{{\theta }_r}$, ${\text{v-cover}}_{{\theta }_r}$, ${\text{v-pack}}_{{\theta }_r}$, and ${\text{e-cover}}_{{\theta }_r}$ that runs in $O(n\cdot \log (n)\cdot m)$ steps. Also, we derive several new Erdős-Pósa-type results from the techniques that we introduce.

arXiv commentSome of the results of this paper have been presented in WAOA 2015