Subexponential time algorithms for finding small tree and path decompositions
Publication date
2015
Authors
Bodlaender, H.L.
Nederlof, Jesper
Editors
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
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.
Keywords
Taverne, General Computer Science, Theoretical Computer Science
Citation
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, 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, conference