Answer Set Solving with Bounded Treewidth Revisited
Authors:
Preprint
Abstract
Parameterized algorithms are a way to solve hard problems more efficiently, given that a specific parameter of the input is small. In this paper, we apply this idea to the field of answer set programming (ASP). To this end, we propose two kinds of graph representations of programs to exploit their treewidth as a parameter. Treewidth roughly measures to which extent the internal structure of a program resembles a tree. Our main contribution is the design of parameterized dynamic programming algorithms, which run in linear time if the treewidth and weights of the given program are bounded. Compared to previous work, our algorithms handle the full syntax of ASP. Finally, we report on an empirical evaluation that shows good runtime behaviour for benchmark instances of low treewidth, especially for counting answer sets.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- ASP-Core-2 Input Language FormatTheory and Practice of Logic Programming, 2019
- Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine LearningJournal of Artificial Intelligence Research, 2017
- Conflict-driven answer set solving: From theory to practiceArtificial Intelligence, 2012
- Answer set programming at a glanceCommunications of the ACM, 2011
- Algorithms for propositional model countingJournal of Discrete Algorithms, 2010
- Heuristic Methods for Hypertree Decomposition2008
- Combinatorial Optimization on Graphs of Bounded TreewidthThe Computer Journal, 2007
- sharpSAT – Counting Models with Advanced Component Caching and Implicit BCP2006
- Subtractive reductions and complete problems for counting complexity classesTheoretical Computer Science, 2005
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986