An O(log OPT)-approximation for covering/packing minor models of θr

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Let CH be the class of graphs containing some fixed graph H as a minor. We define cv H(G) (resp. ce H(G)) as the minimun number of vertices (resp. edges) whose removal from G produces a graph without any subgraph isomorphic to a graph in CH. Also pv H(G) (resp. pe H(G)) is the the maximum number of vertex- (resp. edge-) disjoint subgraphs of G that are isomorphic to some graph in CH. We denote by θr the graph with two vertices and r parallel edges between them. When H = θr, the parameters cv/e H and pv/e H are NP-complete to compute (for sufficiently large r). In this paper we prove a series of combinatorial and algorithmic lemmata that imply that if pv/e θr (G) ≤ k, then cv/e θr (G) = O(k log k). This means that for every r, the class Cθr has the vertex/edge Erdős-Pósa property. Using the combinatorial ideas from our proofs we introduce a unified approach for the design of an O(log OPT)-approximation algorithm for cv θr, pv θr, ce θr and pe θr that runs in O(n ・ log(n) ・ m) steps.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers
EditorsMartin Skutella, Laura Sanità
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783319286839
StatePublished - 2015
Event13th International Workshop on Approximation and Online Algorithms, WAOA 2015 - Patras, Greece
Duration: Sep 17 2015Sep 18 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference13th International Workshop on Approximation and Online Algorithms, WAOA 2015


  • Covering
  • Erdős-Pósa properties
  • Graph packing
  • Minors

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'An O(log OPT)-approximation for covering/packing minor models of θr'. Together they form a unique fingerprint.

Cite this