An $$O(\log \mathrm {OPT})$$ O ( log OPT ) -Approximation for Covering and Packing Minor Models of $$\theta _r$$ θ r
Dimitris Chatzidimitriou, Jean‐Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos · Algorithmica · 2017
Given two graphs G and H, we define $$\mathsf{v}\hbox {-}\mathsf{cover}_{H}(G)$$ (resp. $$\mathsf{e}\hbox {-}\mathsf{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 $$\mathsf{v}\hbox {-}\mathsf{pack}_{H}(G)$$ (resp. $$\mathsf{e}\hbox {-}\mathsf{pack}_{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 $$\mathsf{v}\hbox {-}\mathsf{cover}_{H}$$ , $$\mathsf{e}\hbox {-}\mathsf{cover}_{H}$$ , $$\mathsf{v}\hbox {-}\mathsf{pack}_{H}$$ , and $$\mathsf{e}\hbox {-}\mathsf{pack}_{H}$$ are NP-hard to compute (for sufficiently big values of r). Drawing upon combinatorial results in Chatzidimitriou et al. (Minors in graphs of large $$\theta _r$$ -girth, 2015, arXiv:1510.03041 ), we give an algorithmic proof that if $$\mathsf{v}\hbox {-}\mathsf{pack}_{{\theta _{r}}}(G)\le k$$ , then $$\mathsf{v}\hbox {-}\mathsf{cover}_{\theta _{r}}(G) = O(k\log k)$$ , and similarly for $$\mathsf{e}\hbox {-}\mathsf{pack}_{\theta _{r}}$$ and $$\mathsf{e}\hbox {-}\mathsf{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 $$\mathsf{v}\hbox {-}\mathsf{pack}_{{\theta _{r}}}$$ , $$\mathsf{v}\hbox {-}\mathsf{cover}_{{\theta _{r}}}$$ , $$\mathsf{e}\hbox {-}\mathsf{pack}_{{\theta _{r}}}$$ , and $$\mathsf{e}\hbox {-}\mathsf{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.