Résumé
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 Erdos-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 {\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 Erdos-Pósa-type results from the techniques that we introduce.