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

DOI10.1007/978-3-030-63072-0_6zbMATH Open1479.05294arXiv1912.09144OpenAlexW2995115154MaRDI QIDQ2056889FDOQ2056889

Authors: Ernst Althaus, Sarah Ziegler 

Publication date: 8 December 2021

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.

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

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

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)

Cites Work

• Fundamentals of parameterized complexity
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Parametrized complexity theory.
• Parameterized algorithms
• Title not available (Why is that?)
• An improved algorithm for finding tree decompositions of small width
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm

Cited In (5)

• Faster parameterized algorithms for modification problems to minor-closed classes
• Twin-treewidth: a single-exponential logic-based approach
• Measuring power in coalitional games with friends, enemies and allies
• An FPT 2-approximation for tree-cut decomposition
• 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)