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

Dimitris Chatzidimitriou, Jean Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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(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 languageEnglish (US)
Pages (from-to)1330-1356
Number of pages27
Issue number4
StatePublished - Apr 1 2018


  • 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


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.

Cite this