# Answer Set Solving with Bounded Treewidth Revisited

arXiv: https://arxiv.org/abs/1702.02890 · HTML: https://mlsanity.com/paper/1702.02890/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2017.

## Built on by (most cited first, 9 of 9)

- [Rushing and Strolling among Answer Sets -- Navigation Made Easy](https://mlsanity.com/paper/2112.07596/) (2021)
- [Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?](https://mlsanity.com/paper/2210.03553/) (2022)
- [Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling](https://mlsanity.com/paper/2205.07537/) (2022)
- [Exact ASP Counting with Compact Encodings](https://mlsanity.com/paper/2312.11936/) (2023)
- [IASCAR: Incremental Answer Set Counting by Anytime Refinement](https://mlsanity.com/paper/2311.07233/) (2023)
- [Counting and Reasoning with Plans](https://mlsanity.com/paper/2502.00145/) (2025)
- [Solving Projected Model Counting by Utilizing Treewidth and its Limits](https://mlsanity.com/paper/2305.19212/) (2023)
- [Answer Set Counting and its Applications](https://mlsanity.com/paper/2502.09231/) (2025)
- [Counting Answer Sets of Disjunctive Answer Set Programs](https://mlsanity.com/paper/2507.11655/) (2025)

## Abstract (arXiv)

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.