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.
|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|
|Publication status||Published - 2015|
|Name||Lecture Notes in Computer Science|