Answer set solving with bounded treewidth revisited

DOI10.1007/978-3-319-61660-5_13MaRDI QIDQ2401930zbMATH OpenOpenAlexFDO

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

Publication date 5 September 2017

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

zbMATH Keywords

parameterized algorithmstree decompositions

Mathematics Subject Classification ID

Logic programming (68N17) Graph theory (including graph drawing) in computer science (68R10) Knowledge representation (68T30) Analysis of algorithms (68W40)

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.

Recommendations

• Constraint Satisfaction with Bounded Treewidth Revisited
• Constraint satisfaction with bounded treewidth revisited
• Tractable answer-set programming with weight constraints: bounded treewidth is not enough
• Treewidth in non-ground answer set solving and alliance problems in graphs
• The impact of treewidth on grounding and solving of answer set programs
• Bounded Tree-Width and CSP-Related Problems
• Complexity results for answer set programming with bounded predicate arities and implications
• Treewidth and counting projected answer sets
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics

Cited in

(18)

• A multiparametric view on answer set programming
• Treewidth and counting projected answer sets
• Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
• Solving projected model counting by utilizing treewidth and its limits
• Clique-width and directed width measures for answer-set programming
• The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
• Weighted model counting on the GPU by exploiting small treewidth
• DynASP2.5: Dynamic Programming on Tree Decompositions in Action
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• The impact of treewidth on grounding and solving of answer set programs
• Treewidth in non-ground answer set solving and alliance problems in graphs
• Tractable answer-set programming with weight constraints: bounded treewidth is not enough
• Default logic and bounded treewidth
• Reasoning in assumption-based argumentation using tree-decompositions
• IASCAR: incremental answer set counting by anytime refinement
• Decomposition strategies and multi-shot ASP solving for job-shop scheduling
• A fast and accurate ASP counting based network reliability estimator
• Constraint satisfaction with bounded treewidth revisited

This page was built for publication: Answer set solving with bounded treewidth revisited

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