## Abstract

Given two graphs G and H, we define v- cover_{H}(G) (resp. e- 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 v- pack_{H}(G) (resp. e- 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 θ_{r} the graph with two vertices and r parallel edges between them. When H= θ_{r}, the parameters v- cover_{H}, e- cover_{H}, v- pack_{H}, and e- 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 θ_{r}-girth, 2015, arXiv:1510.03041), we give an algorithmic proof that if v-packθr(G)≤k, then v-coverθr(G)=O(klogk), 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 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 OPT) -approximation algorithm for v-packθr, v-coverθr, e-packθr, and e-coverθr that runs in O(n· log (n) · m) steps. Also, we derive several new Erdős–Pósa-type results from the techniques that we introduce.

Original language | English (US) |
---|---|

Pages (from-to) | 1330-1356 |

Number of pages | 27 |

Journal | Algorithmica |

Volume | 80 |

Issue number | 4 |

DOIs | |

State | Published - Apr 1 2018 |

## Keywords

- Approximation algorithms
- Coverings in graphs
- Erdős–Pósa property
- Minor-models of θ
- Packings in graphs
- Protrusion decomposition

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics

## Fingerprint

Dive into the research topics of 'An O(log OPT)-Approximation for Covering and Packing Minor Models of θ_{r}'. Together they form a unique fingerprint.