Subexponential time algorithms for finding small tree and path decompositions

H.L. Bodlaender; J. Nederlof

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

Subexponential time algorithms for finding small tree and path decompositions

H.L. Bodlaender
, J. Nederlof

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

6 Citations (Scopus)

Abstract

The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex 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/ logn) time and show that they cannot be solved in 2^o(n / logn) time, assuming the Exponential Time Hypothesis.

Original language	English
Title of host publication	Algorithms - ESA 2015 (23rd Annual European Symposium, Patras, Greece, September 14-16, 2015)
Editors	N. Bansal, I. Finocchi
Place of Publication	Berlin
Publisher	Springer
Pages	179-190
ISBN (Print)	978-3-662-48349-7
DOIs	https://doi.org/10.1007/978-3-662-48350-3_16
Publication status	Published - 2015

Publication series

Name	Lecture Notes in Computer Science
Volume	9294
ISSN (Print)	0302-9743

Access to Document

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

Cite this

@inproceedings{92f925c0ae774f7faaafc881e093b6ca,

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 n-vertex 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\textasciicircum{}O(n/ logn) time and show that they cannot be solved in 2\textasciicircum{}o(n / logn) time, assuming the Exponential Time Hypothesis.",

author = "H.L. Bodlaender and J. Nederlof",

year = "2015",

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

language = "English",

isbn = "978-3-662-48349-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "179--190",

editor = "N. Bansal and I. Finocchi",

booktitle = "Algorithms - ESA 2015 (23rd Annual European Symposium, Patras, Greece, September 14-16, 2015)",

address = "Germany",

}

Subexponential time algorithms for finding small tree and path decompositions. / Bodlaender, H.L.; Nederlof, J.
Algorithms - ESA 2015 (23rd Annual European Symposium, Patras, Greece, September 14-16, 2015). ed. / N. Bansal; I. Finocchi. Berlin: Springer, 2015. p. 179-190 (Lecture Notes in Computer Science; 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, H.L.

AU - Nederlof, J.

PY - 2015

Y1 - 2015

N2 - The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex 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/ logn) time and show that they cannot be solved in 2^o(n / logn) time, assuming the Exponential Time Hypothesis.

AB - The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex 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/ logn) time and show that they cannot be solved in 2^o(n / logn) time, assuming the Exponential Time Hypothesis.

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

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

M3 - Conference contribution

SN - 978-3-662-48349-7

T3 - Lecture Notes in Computer Science

SP - 179

EP - 190

BT - Algorithms - ESA 2015 (23rd Annual European Symposium, Patras, Greece, September 14-16, 2015)

A2 - Bansal, N.

A2 - Finocchi, I.

PB - Springer

CY - Berlin

ER -

Subexponential time algorithms for finding small tree and path decompositions

Abstract

Publication series

Access to Document

Fingerprint

Cite this