DynASP2.5: Dynamic Programming on Tree Decompositions in Action

DOI10.4230/LIPICS.IPEC.2017.17zbMATH Open1443.68164arXiv1706.09370OpenAlexW2963867061MaRDI QIDQ5111876FDOQ5111876

Johannes K. Fichte, Markus Hecher, Michael Morak, Stefan Woltran

Publication date: 27 May 2020

Abstract: A vibrant theoretical research area are efficient exact parameterized algorithms. Very recent solving competitions such as the PACE challenge show that there is also increasing practical interest in the parameterized algorithms community. An important research question is whether dedicated parameterized exact algorithms exhibit certain practical relevance and one can even beat well-established problem solvers. We consider the logic-based declarative modeling language and problem solving framework Answer Set Programming (ASP). State-of-the-art ASP solvers rely considerably on Sat-based algorithms. An ASP solver (DynASP2), which is based on a classical dynamic programming on tree decompositions, has been published very recently. Unfortunately, DynASP2 can outperform modern ASP solvers on programs of small treewidth only if the question of interest is to count the number of solutions. In this paper, we describe underlying concepts of our new implementation (DynASP2.5) that shows competitive behavior to state-of-the-art ASP solvers even for finding just one solution when solving problems as the Steiner tree problem that have been modeled in ASP on graphs with low treewidth. Our implementation is based on a novel approach that we call multi-pass dynamic programming (M-DPSINC).

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

Recommendations

• Practical access to dynamic programming on tree decompositions
• Practical access to dynamic programming on tree decompositions
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Dynamic programming and planarity: improved tree-decomposition based algorithms
• The D-FLAT system for dynamic programming on tree decompositions
• scientific article; zbMATH DE number 4060712
• Revisiting dynamic programming for finding optimal subtrees in trees
• Dynamic programming for spanning tree problems: application to the multi-objective case
• Tree Decompositions of Graphs: Saving Memory in Dynamic Programming

zbMATH Keywords

parameterized algorithmstree decompositionsmulti-pass dynamic programmingfixed-parameter linear time

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Dynamic programming (90C39) Nonnumerical algorithms (68W05) Logic programming (68N17) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• DynASP2.5: Dynamic Programming on Tree Decompositions in Action
• Extending and implementing the stable model semantics
• On the computational cost of disjunctive logic programming: Propositional case
• Courcelle's theorem -- a game-theoretic approach
• Conflict-driven answer set solving: from theory to practice
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning
• Answer set solving with bounded treewidth revisited
• The Impact of Treewidth on Grounding and Solving of Answer Set Programs
• Title not available (Why is that?)
• Anytime answer set optimization via unsatisfiable core shrinking
• D-FLAT^2: Subset Minimization in Dynamic Programming on Tree Decompositions Made Easy

Cited In (11)

• Aspmc: new frontiers of algebraic answer set counting
• A multiparametric view on answer set programming
• Solving projected model counting by utilizing treewidth and its limits
• Title not available (Why is that?)
• DynASP2.5: Dynamic Programming on Tree Decompositions in Action
• dynASP
• Testing in ASP: revisited language and programming environment
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Default logic and bounded treewidth

This page was built for publication: DynASP2.5: Dynamic Programming on Tree Decompositions in Action

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