Given two graphs $G$ and $H$, we define $\textsf{ v-cover}_{ H}(G)$ (resp. $\textsf{ 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 $\textsf{ v-pack}_{ H}(G)$ (resp. $\textsf{ 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 $\textsf{ v-cover}_{ H}$, $\textsf{ e-cover}_{ H}$, $\textsf{ v-pack}_{ H}$, and $\textsf{ 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 $\textsf{ v-pack}_{ \theta_r}(G)\leq k$, then $\textsf{ v-cover}_{ \theta_r}(G) = O(k\log k)$, and similarly for $\textsf{ v-pack}_{ \theta_r}$ and $\textsf{ e-cover}_{ \theta_r}$. In other words, the class of graphs containing ${ \theta_r}$ as a minor has the vertex/edge Erd\H{ o}s-P\'osa 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 { \rm OPT})$-approximation algorithm for $\textsf{ v-pack}_{ \theta_r}$, $\textsf{ v-cover}_{ \theta_r}$, $\textsf{ v-pack}_{ \theta_r}$, and $\textsf{ e-cover}_{ \theta_r}$ that runs in $O(n\cdot \log(n)\cdot m)$ steps. Also, we derive several new Erd\H{ o}s-P\'osa-type results from the techniques that we introduce.
Categories: cs.DS math.CO