Optimal tree decompositions revisited: a simpler linear-time FPT algorithm

DOI10.1007/978-3-030-63072-0_6MaRDI QIDQ2056889zbMATH OpenOpenAlexFDO

Authors Ernst Althaus, Sarah Ziegler

Publication date 8 December 2021

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

zbMATH Keywords

parametrized complexitytree decompositionssimplified description

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Abstract: In 1996, Bodlaender showed the celebrated result that an optimal tree decomposition of a graph of bounded treewidth can be found in linear time. The algorithm is based on an algorithm of Bodlaender and Kloks that computes an optimal tree decomposition given a non-optimal tree decomposition of bounded width. Both algorithms, in particular the second, are hardly accessible. In our review, we present them in a much simpler way than the original presentations. In our description of the second algorithm, we start by explaining how all tree decompositions of subtrees defined by the nodes of the given tree decomposition can be enumerated. We group tree decompositions into equivalence classes depending on the current node of the given tree decomposition, such that it suffices to enumerate one tree decomposition per equivalence class and, for each node of the given tree decomposition, there are only a constant number of classes which can be represented in constant space. Our description of the first algorithm further simplifies Perkovic and Reed's simplification.

Recommendations

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Computing Optimal Hypertree Decompositions
• FPT and kernelization algorithms for the induced tree problem
• On the power of tree-depth for fully polynomial FPT algorithms
• scientific article; zbMATH DE number 1670677
• scientific article; zbMATH DE number 7310159
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• An improved algorithm for finding tree decompositions of small width

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• An improved algorithm for finding tree decompositions of small width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Fundamentals of parameterized complexity
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• Parameterized algorithms
• Parametrized complexity theory.

Cited in

(4)

• Twin-treewidth: a single-exponential logic-based approach
• Faster parameterized algorithms for modification problems to minor-closed classes
• Measuring power in coalitional games with friends, enemies and allies
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm

This page was built for publication: Optimal tree decompositions revisited: a simpler linear-time FPT algorithm

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