Practical access to dynamic programming on tree decompositions
type: Item
instance of: scholarly article
title: Practical access to dynamic programming on tree decompositions
zbMATH Open document ID: 1461.68091
author: Max Bannach
author: Sebastian Berndt
published in: Algorithms
publication date: 2020-10-08T00:00:00Z
review text: Summary: Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood. We investigate the practicability of one of the fundamental approaches of this field: dynamic programming on tree decompositions. Indisputably, this is a key technique in parameterized algorithms and modern algorithm design. Despite the enormous impact of this approach in theory, it still has very little influence on practical implementations. The reasons for this phenomenon are manifold. One of them is the simple fact that such an implementation requires a long chain of non-trivial tasks (as computing the decomposition, preparing it, \dots). We provide an easy way to implement such dynamic programs that only requires the definition of the update rules. With this interface, dynamic programs for various problems, such as 3-coloring, can be implemented easily in about 100 lines of structured Java code. The theoretical foundation of the success of dynamic programming on tree decompositions is well understood due to Courcelle's celebrated theorem, which states that every MSO-definable problem can be efficiently solved if a tree decomposition of small width is given. We seek to provide practical access to this theorem as well, by presenting a lightweight model checker for a small fragment of MSO\(_1\) (that is, we do not consider ``edge-set-based'' problems). This fragment is powerful enough to describe many natural problems, and our model checker turns out to be very competitive against similar state-of-the-art tools.
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 7257792
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: treewidth
zbMATH Keywords: model checking
describes a project that uses: D-FLAT
describes a project that uses: Jdrasil
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a12080172
OpenAlex ID: W2967340447
cites work: Parameterized Algorithms
cites work: Q5111890
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Positive-instance driven dynamic programming for treewidth
cites work: Parametrized complexity theory.
cites work: Jdrasil: A Modular Library for Computing Tree Decompositions
cites work: The complexity of first-order and monadic second-order logic revisited
cites work: Courcelle's theorem -- a game-theoretic approach
cites work: SAT-based local improvement for finding tree decompositions of small width
Wikidata QID: Q127355601
DOI: 10.3390/A12080172
description: scientific article; zbMATH DE number 7257792