An $O(log OPT)$-Approximation for Covering/Packing Minor Models of $θ _r$

Abstract : Given two graphs $G$ and $H$, we define $\mathrm{vcover}_{H}(G)$ (resp. $\mathrm{ecover}_{H}(G)$) as the minimum number of vertices (resp. edges) whose removal from $G$ produces a graph without any minor isomorphic to ${H}$. Also $\mathrm{vpack}_{H}(G)$ (resp. $\mathrm{epack}_{H}(G)$) is the maximum number of vertex- (resp. edge-) disjoint subgraphs of $G$ that contain a minor isomorphic to $H$. We denote by $\theta_{r}$ the graph with two vertices and $r$ parallel edges between them. When $H=\theta_{r}$, the parameters $\mathrm{vcover}_{H}$, $\mathrm{ecover}_{H}$, $\mathrm{vpack}_{H}$, and $\mathrm{epack}_{H}$ are {\sf NP}-hard to compute (for sufficiently big values of $r$). Drawing upon combinatorial results in \cite{ChatzidimitriouRST15mino}, we give an algorithmic proof that if $\mathrm{vpack}_{{\theta_{r}}}(G)\leq k$, then $\mathrm{vcover}_{\theta_{r}}(G) = O(k\log k)$, and similarly for $\mathrm{epack}_{\theta_{r}}$ and $\mathrm{ecover}_{\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 {\rm OPT})$-approximation algorithm for $\mathrm{vpack}_{\theta_r}$, $\mathrm{vcover}_{\theta_r}$, $\mathrm{epack}_{\theta_r}$, and $\mathrm{ecover}_{\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.
Type de document :
Communication dans un congrès
WAOA: Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. Springer International Publishing, 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers, LNCS (9499), pp.122-132, 2016, 〈10.1007/978-3-319-28684-6_11〉
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-01218496
Contributeur : Jean-Florent Raymond <>
Soumis le : mercredi 21 octobre 2015 - 12:06:55
Dernière modification le : jeudi 15 novembre 2018 - 15:26:36
Document(s) archivé(s) le : vendredi 22 janvier 2016 - 19:03:16

Fichier

pumpkilAlgo.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. An $O(log OPT)$-Approximation for Covering/Packing Minor Models of $θ _r$. WAOA: Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. Springer International Publishing, 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers, LNCS (9499), pp.122-132, 2016, 〈10.1007/978-3-319-28684-6_11〉. 〈hal-01218496〉

Partager

Métriques

Consultations de la notice

362

Téléchargements de fichiers

36