Subexponential time algorithms for finding small tree and path decompositions

Hans L. Bodlaender; Jesper Nederlof

doi:10.1007/978-3-662-48350-3_16

Subexponential time algorithms for finding small tree and path decompositions

Hans L. Bodlaender^*, Jesper Nederlof

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given nvertex graph G and integer k, what is the minimum number of bags of a tree decomposition (respectively, path decomposition) of width at most k. The problems are known to be NP-complete for each fixed k ≥ 4. In this paper we present algorithms that solve both problems for fixed k in 2^{O(n/ log n)} time and show that they cannot be solved in 2^{o(n/ log n)} time, assuming the Exponential Time Hypothesis.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Pages	179-190
Number of pages	12
Volume	9294
ISBN (Print)	9783662483497
DOIs	https://doi.org/10.1007/978-3-662-48350-3_16
Publication status	Published - 2015
Event	23rd European Symposium on Algorithms, ESA 2015 - Patras, Greece Duration: 14 Sept 2015 → 16 Sept 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9294
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	23rd European Symposium on Algorithms, ESA 2015
Country/Territory	Greece
City	Patras
Period	14/09/15 → 16/09/15

Access to Document

10.1007/978-3-662-48350-3_16

978-3-662-48350-3_16Final published version, 276 KBLicence: Taverne

Cite this

Bodlaender, H. L., & Nederlof, J. (2015). Subexponential time algorithms for finding small tree and path decompositions. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 9294, pp. 179-190). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294). Springer. https://doi.org/10.1007/978-3-662-48350-3_16

Bodlaender, Hans L. ; Nederlof, Jesper. / Subexponential time algorithms for finding small tree and path decompositions. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 9294 Springer, 2015. pp. 179-190 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6804865225164648bdc3f70a88fbd0dc,

title = "Subexponential time algorithms for finding small tree and path decompositions",

abstract = "The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given nvertex graph G and integer k, what is the minimum number of bags of a tree decomposition (respectively, path decomposition) of width at most k. The problems are known to be NP-complete for each fixed k ≥ 4. In this paper we present algorithms that solve both problems for fixed k in 2O(n/ log n) time and show that they cannot be solved in 2o(n/ log n) time, assuming the Exponential Time Hypothesis.",

author = "Bodlaender, {Hans L.} and Jesper Nederlof",

year = "2015",

doi = "10.1007/978-3-662-48350-3_16",

language = "English",

isbn = "9783662483497",

volume = "9294",

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

publisher = "Springer",

pages = "179--190",

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

note = "23rd European Symposium on Algorithms, ESA 2015 ; Conference date: 14-09-2015 Through 16-09-2015",

}

Bodlaender, HL & Nederlof, J 2015, Subexponential time algorithms for finding small tree and path decompositions. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 9294, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9294, Springer, pp. 179-190, 23rd European Symposium on Algorithms, ESA 2015, Patras, Greece, 14/09/15. https://doi.org/10.1007/978-3-662-48350-3_16

Subexponential time algorithms for finding small tree and path decompositions. / Bodlaender, Hans L.; Nederlof, Jesper.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 9294 Springer, 2015. p. 179-190 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Subexponential time algorithms for finding small tree and path decompositions

AU - Bodlaender, Hans L.

AU - Nederlof, Jesper

PY - 2015

Y1 - 2015

N2 - The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given nvertex graph G and integer k, what is the minimum number of bags of a tree decomposition (respectively, path decomposition) of width at most k. The problems are known to be NP-complete for each fixed k ≥ 4. In this paper we present algorithms that solve both problems for fixed k in 2O(n/ log n) time and show that they cannot be solved in 2o(n/ log n) time, assuming the Exponential Time Hypothesis.

AB - The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given nvertex graph G and integer k, what is the minimum number of bags of a tree decomposition (respectively, path decomposition) of width at most k. The problems are known to be NP-complete for each fixed k ≥ 4. In this paper we present algorithms that solve both problems for fixed k in 2O(n/ log n) time and show that they cannot be solved in 2o(n/ log n) time, assuming the Exponential Time Hypothesis.

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

U2 - 10.1007/978-3-662-48350-3_16

DO - 10.1007/978-3-662-48350-3_16

M3 - Conference contribution

AN - SCOPUS:84945546494

SN - 9783662483497

VL - 9294

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

SP - 179

EP - 190

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

PB - Springer

T2 - 23rd European Symposium on Algorithms, ESA 2015

Y2 - 14 September 2015 through 16 September 2015

ER -

Bodlaender HL , Nederlof J. Subexponential time algorithms for finding small tree and path decompositions. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 9294. Springer. 2015. p. 179-190. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48350-3_16

Subexponential time algorithms for finding small tree and path decompositions

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this