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.
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download
Contributor : Jean-Florent Raymond <>
Submitted on : Wednesday, October 21, 2015 - 12:06:55 PM
Last modification on : Thursday, April 18, 2019 - 7:46:02 PM
Long-term archiving on : Friday, January 22, 2016 - 7:03:16 PM


Files produced by the author(s)




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. pp.122-132, ⟨10.1007/978-3-319-28684-6_11⟩. ⟨hal-01218496⟩



Record views


Files downloads