1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor

Erik D. Demaine; Mohammad Taghi Hajiaghayi; Dimitrios M. Thilikos

doi:10.1007/3-540-45753-4_8

1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor

Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos

Computer Science

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

Abstract

We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K₅-minorfree graphs and K_3,3-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most c_H (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs.

Original language	English (US)
Title of host publication	Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings
Editors	Klaus Jansen, Stefano Leonardi, Vijay Vazirani
Publisher	Springer Verlag
Pages	67-80
Number of pages	14
ISBN (Print)	3540441867, 9783540441861
DOIs	https://doi.org/10.1007/3-540-45753-4_8
State	Published - 2002
Event	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 - Rome, Italy Duration: Sep 17 2002 → Sep 21 2002

Publication series

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

Conference

Conference	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002
Country/Territory	Italy
City	Rome
Period	9/17/02 → 9/21/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-45753-4_8

Cite this

Demaine, E. D., Hajiaghayi, M. T., & Thilikos, D. M. (2002). 1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor. In K. Jansen, S. Leonardi, & V. Vazirani (Eds.), Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings (pp. 67-80). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2462). Springer Verlag. https://doi.org/10.1007/3-540-45753-4_8

1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor. / Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M.
Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. ed. / Klaus Jansen; Stefano Leonardi; Vijay Vazirani. Springer Verlag, 2002. p. 67-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2462).

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

Demaine, ED, Hajiaghayi, MT & Thilikos, DM 2002, 1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor. in K Jansen, S Leonardi & V Vazirani (eds), Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2462, Springer Verlag, pp. 67-80, 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002, Rome, Italy, 9/17/02. https://doi.org/10.1007/3-540-45753-4_8

Demaine ED, Hajiaghayi MT, Thilikos DM. 1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor. In Jansen K, Leonardi S, Vazirani V, editors, Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. Springer Verlag. 2002. p. 67-80. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45753-4_8

Demaine, Erik D. ; Hajiaghayi, Mohammad Taghi ; Thilikos, Dimitrios M. / 1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor. Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. editor / Klaus Jansen ; Stefano Leonardi ; Vijay Vazirani. Springer Verlag, 2002. pp. 67-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5c37b1b3a3c140f8a0a83b408443739d,

title = "1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor",

abstract = "We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K5-minorfree graphs and K3,3-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most cH (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs.",

author = "Demaine, {Erik D.} and Hajiaghayi, {Mohammad Taghi} and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

year = "2002",

doi = "10.1007/3-540-45753-4_8",

language = "English (US)",

isbn = "3540441867",

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

publisher = "Springer Verlag",

pages = "67--80",

editor = "Klaus Jansen and Stefano Leonardi and Vijay Vazirani",

booktitle = "Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings",

}

TY - GEN

T1 - 1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor

AU - Demaine, Erik D.

AU - Hajiaghayi, Mohammad Taghi

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K5-minorfree graphs and K3,3-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most cH (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs.

AB - We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K5-minorfree graphs and K3,3-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and graphs of treewidth at most cH (a constant dependent on H) using clique sums. This result has several applications in designing fully polynomial-time approximation schemes and fixed-parameter algorithms for many NP-complete problems on these graphs.

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

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

U2 - 10.1007/3-540-45753-4_8

DO - 10.1007/3-540-45753-4_8

M3 - Conference contribution

AN - SCOPUS:84861199200

SN - 3540441867

SN - 9783540441861

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

SP - 67

EP - 80

BT - Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings

A2 - Jansen, Klaus

A2 - Leonardi, Stefano

A2 - Vazirani, Vijay

PB - Springer Verlag

T2 - 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

1.5-approximation for treewidth of graphs excluding a graph with one crossing as a minor

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this