摘要

Given two graphs G and H, we define v-coverH(G) (resp. e-coverH(G)) as the minimum number of vertices (resp. edges) whose removal from G produces a graph without any minor isomorphic to H. Also v-packH(G) (resp. e-packH(G)) is the maximum number of vertex-(resp. edge-) disjoint subgraphs of G that contain a minor isomorphic to H. We denote by.r the graph with two vertices and r parallel edges between them. When H =.r, the parameters v-coverH, e-coverH, v-packH, and e-packH are NP-hard to compute (for sufficiently big values of r). Drawing upon combinatorial results in Chatzidimitriou et al. (Minors in graphs of large.r -girth, 2015, arXiv: 1510.03041), we give an algorithmic proof that if v-pack.r (G) = k, then v-cover.r (G) = O(k log k), and similarly for e-pack.r and e-cover.r. In other words, the class of graphs containing.r as a minor has the vertex/ edge Erdos-Posa property, for every positive integer r. Using the algorithmic machinery of our proofs we introduce a unified approach for the design of an O(logOPT)-approximation algorithm for v-pack.r, v-cover.r, e-pack.r, and e-cover.r that runs in O(n center dot log(n) center dot m) steps. Also, we derive several new Erdos-Posa-type results from the techniques that we introduce.

  • 出版日期2018-4