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

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

doi:10.1007/978-3-319-28684-6_11

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

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Let C_H be the class of graphs containing some fixed graph H as a minor. We define c^v _H(G) (resp. c^e _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 C_H. Also p^v _H(G) (resp. p^e _H(G)) is the the maximum number of vertex- (resp. edge-) disjoint subgraphs of G that are isomorphic to some graph in C_H. We denote by θ_r the graph with two vertices and r parallel edges between them. When H = θ_r, the parameters c^v/e _H and p^v/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 p^v/e _θr (G) ≤ k, then c^v/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 c^v _θr, p^v _θr, c^e _θr and p^e _θr that runs in O(n ・ log(n) ・ m) steps.

Original language	English (US)
Title of host publication	Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers
Editors	Martin Skutella, Laura Sanità
Publisher	Springer Verlag
Pages	122-132
Number of pages	11
ISBN (Print)	9783319286839
DOIs	https://doi.org/10.1007/978-3-319-28684-6_11
State	Published - 2015
Event	13th International Workshop on Approximation and Online Algorithms, WAOA 2015 - Patras, Greece Duration: Sep 17 2015 → Sep 18 2015

Publication series

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

Conference

Conference	13th International Workshop on Approximation and Online Algorithms, WAOA 2015
Country/Territory	Greece
City	Patras
Period	9/17/15 → 9/18/15

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-28684-6_11

Cite this

Chatzidimitriou, D., Raymond, J. F., Sau, I., & Thilikos, D. M. (2015). An O(log OPT)-approximation for covering/packing minor models of θ_r In M. Skutella, & L. Sanità (Eds.), Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers (pp. 122-132). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9499). Springer Verlag. https://doi.org/10.1007/978-3-319-28684-6_11

An O(log OPT)-approximation for covering/packing minor models of θ_r . / Chatzidimitriou, Dimitris; Raymond, Jean Florent; Sau, Ignasi et al.
Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers. ed. / Martin Skutella; Laura Sanità. Springer Verlag, 2015. p. 122-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9499).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chatzidimitriou, D, Raymond, JF, Sau, I & Thilikos, DM 2015, An O(log OPT)-approximation for covering/packing minor models of θ_r in M Skutella & L Sanità (eds), Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9499, Springer Verlag, pp. 122-132, 13th International Workshop on Approximation and Online Algorithms, WAOA 2015, Patras, Greece, 9/17/15. https://doi.org/10.1007/978-3-319-28684-6_11

Chatzidimitriou D, Raymond JF, Sau I, Thilikos DM. An O(log OPT)-approximation for covering/packing minor models of θ_r In Skutella M, Sanità L, editors, Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers. Springer Verlag. 2015. p. 122-132. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-28684-6_11

Chatzidimitriou, Dimitris ; Raymond, Jean Florent ; Sau, Ignasi et al. / An O(log OPT)-approximation for covering/packing minor models of θ_r Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers. editor / Martin Skutella ; Laura Sanità. Springer Verlag, 2015. pp. 122-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a72464b0b4464d44bb4b0434174f31b8,

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

abstract = "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{\H o}s-P{\'o}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.",

keywords = "Covering, Erd{\H o}s-P{\'o}sa properties, Graph packing, Minors",

author = "Dimitris Chatzidimitriou and Raymond, {Jean Florent} and Ignasi Sau and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 13th International Workshop on Approximation and Online Algorithms, WAOA 2015 ; Conference date: 17-09-2015 Through 18-09-2015",

year = "2015",

doi = "10.1007/978-3-319-28684-6_11",

language = "English (US)",

isbn = "9783319286839",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "122--132",

editor = "Martin Skutella and Laura Sanit{\`a}",

booktitle = "Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers",

}

TY - GEN

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

AU - Chatzidimitriou, Dimitris

AU - Raymond, Jean Florent

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Covering

KW - Erdős-Pósa properties

KW - Graph packing

KW - Minors

UR - http://www.scopus.com/inward/record.url?scp=84956626661&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84956626661&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-28684-6_11

DO - 10.1007/978-3-319-28684-6_11

M3 - Conference contribution

AN - SCOPUS:84956626661

SN - 9783319286839

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 122

EP - 132

BT - Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers

A2 - Skutella, Martin

A2 - Sanità, Laura

PB - Springer Verlag

T2 - 13th International Workshop on Approximation and Online Algorithms, WAOA 2015

Y2 - 17 September 2015 through 18 September 2015

ER -