Subexponential time algorithms for finding small tree and path decompositions

DOI10.1007/978-3-662-48350-3_16MaRDI QIDQ3452781zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Jesper Nederlof, Hans L. Bodlaender

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.02415

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Multi-objective and goal programming (90C29) Programming involving graphs or networks (90C35)

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 G of width at most k. The problems are known to be NP-complete for each fixed $kgeq4$. 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.

Recommendations

• Minimum size tree-decompositions
• Minimum size tree-decompositions
• An improved algorithm for finding tree decompositions of small width
• Algorithms finding tree-decompositions of graphs
• Approximate tree decompositions of planar graphs in linear time

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Exact algorithms for intervalizing colored graphs
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Minimum size tree-decompositions
• Partition into triangles on bounded degree graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The complexity of satisfiability problems
• The number of trees
• Treewidth. Computations and approximations
• Which problems have strongly exponential complexity?

Cited in

(7)

• On tradeoffs between width- and fill-like graph parameters
• Finding small separators in linear time via treewidth reduction
• scientific article; zbMATH DE number 1420905 (Why is no real title available?)
• Improved lower bounds for graph embedding problems
• Minimum size tree-decompositions
• Minimum size tree-decompositions
• Complexity of token swapping and its variants

This page was built for publication: Subexponential time algorithms for finding small tree and path decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452781)