Contraction obstructions for treewidth

Fedor V. Fomin; Petr Golovach; Dimitrios M. Thilikos

doi:10.1016/j.jctb.2011.02.008

Contraction obstructions for treewidth

Fedor V. Fomin, Petr Golovach, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as "obstruction patterns" for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.

Original language	English (US)
Pages (from-to)	302-314
Number of pages	13
Journal	Journal of Combinatorial Theory. Series B
Volume	101
Issue number	5
DOIs	https://doi.org/10.1016/j.jctb.2011.02.008
State	Published - Sep 2011

Keywords

Bidimensionality
Graph contraction
Graph minor
Treewidth

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2011.02.008

Cite this

@article{56e958142f8441458e6e7ad99acd2f5d,

title = "Contraction obstructions for treewidth",

abstract = "We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as {"}obstruction patterns{"} for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.",

keywords = "Bidimensionality, Graph contraction, Graph minor, Treewidth",

author = "Fomin, {Fedor V.} and Petr Golovach and Thilikos, {Dimitrios M.}",

year = "2011",

month = sep,

doi = "10.1016/j.jctb.2011.02.008",

language = "English (US)",

volume = "101",

pages = "302--314",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

T1 - Contraction obstructions for treewidth

AU - Fomin, Fedor V.

AU - Golovach, Petr

AU - Thilikos, Dimitrios M.

PY - 2011/9

Y1 - 2011/9

N2 - We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as "obstruction patterns" for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.

AB - We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as "obstruction patterns" for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.

KW - Bidimensionality

KW - Graph contraction

KW - Graph minor

KW - Treewidth

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

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

U2 - 10.1016/j.jctb.2011.02.008

DO - 10.1016/j.jctb.2011.02.008

M3 - Article

AN - SCOPUS:79956285587

SN - 0095-8956

VL - 101

SP - 302

EP - 314

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 5

ER -

Contraction obstructions for treewidth

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this