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

摘要

AbstractGiven two graphsGandH, we define$$mathsf{v}hbox {-}mathsf{cover}_{H}(G)$$v-coverH(G)(resp.$$mathsf{e}hbox {-}mathsf{cover}_{H}(G)$$e-coverH(G)) as the minimum number of vertices (resp. edges) whose removal fromGproduces a graph without any minor isomorphic toH. Also$$mathsf{v}hbox {-}mathsf{pack}_{H}(G)$$v-packH(G)(resp.$$mathsf{e}hbox {-}mathsf{pack}_{H}(G)$$e-packH(G)) is the maximum number of vertex- (resp. edge-) disjoint subgraphs ofGthat contain a minor isomorphic toH. We denote by$$theta _{r}$$θrthe graph with two vertices andrparallel edges between them. When$$H=theta _{r}$$H=θr, the parameters$$mathsf{v}hbox {-}mathsf{cover}_{H}$$v-coverH,$$mathsf{e}hbox {-}mathsf{cover}_{H}$$e-coverH,$$mathsf{v}hbox {-}mathsf{pack}_{H}$$v-packH, and$$mathsf{e}hbox {-}mathsf{pack}_{H}$$e-packHareNP-hard to compute (for sufficiently big values of r). Drawing upon combinatorial results in Chatzidimitriou et al. (Minors in graphs of large$$theta _r$$θr-girth, 2015,arXiv:1510.03041), we give an algorithmic proof that if$$mathsf{v}hbox {-}mathsf{pack}_{{theta _{r}}}(G)le k$$v-packθr(G)≤k, then$$mathsf{v}hbox {-}mathsf{cover}_{theta _{r}}(G) = O(klog k)$$v-coverθr(G)=O(klogk), and similarly for$$mathsf{e}hbox {-}mathsf{pack}_{theta _{r}}$$e-packθrand $$mathsf{e}hbox {-}mathsf{cover}_{theta _{r}}$$e-coverθr. In other words, the class of graphs containing$${theta _{r}}$$θras a minor has the vertex/edge Erdős–Pósa property, for every positive integerr. Using the algorithmic machinery of our proofs we introduce a unified approach for the design of an$$O(log mathrm{OPT})$$O(logOPT)-approximation algorithm for $$mathsf{v}hbox {-}mathsf{pack}_{{theta _{r}}}$$v-packθr,$$mathsf{v}hbox {-}mathsf{cover}_{{theta _{r}}}$$v-coverθr,$$mathsf{e}hbox {-}mathsf{pack}_{{theta _{r}}}$$e-packθr, and$$mathsf{e}hbox {-}mathsf{cover}_{{theta _{r}}}$$e-coverθrthat runs in$$O(ncdot log (n)cdot m)$$O(n·log(n)·m)steps. Also, we derive several new Erdős–Pósa-type results from the techniques that we introduce.