# Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 95 references that are in the map.
- First posted on arXiv 7 Oct 2022.

## Builds on (most cited first, 21 of 21)

- [Multi-shot ASP solving with clingo](https://mlsanity.com/paper/1705.09811/) (2017)
- [ASP-Core-2 Input Language Format](https://mlsanity.com/paper/1911.04326/) (2019)
- [Clingo = ASP + Control: Preliminary Report](https://mlsanity.com/paper/1405.3694/) (2014)
- [The Model Counting Competition 2020](https://mlsanity.com/paper/2012.01323/) (2020)
- [Answer Set Solving with Bounded Treewidth Revisited](https://mlsanity.com/paper/1702.02890/) (2017)
- [A Uniform Treatment of Aggregates and Constraints in Hybrid ASP](https://mlsanity.com/paper/2003.04176/) (2020)
- [Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution](https://mlsanity.com/paper/1401.3868/) (2014)
- [selp: A Single-Shot Epistemic Logic Program Solver](https://mlsanity.com/paper/2001.01089/) (2020)
- [Exploiting Database Management Systems and Treewidth for Counting](https://mlsanity.com/paper/2001.04191/) (2020)
- [eclingo: A solver for Epistemic Logic Programs](https://mlsanity.com/paper/2008.02018/) (2020)
- [Lower Bounds for QBFs of Bounded Treewidth](https://mlsanity.com/paper/1910.01047/) (2019)
- [An ASP semantics for Constraints involving Conditional Aggregates](https://mlsanity.com/paper/2002.06911/) (2020)
- [Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard](https://mlsanity.com/paper/2007.04620/) (2020)
- [A Time Leap Challenge for SAT Solving](https://mlsanity.com/paper/2008.02215/) (2020)
- [DPMC: Weighted Model Counting by Dynamic Programming on Project-Join Trees](https://mlsanity.com/paper/2008.08748/) (2020)
- [Practical Access to Dynamic Programming on Tree Decompositions](https://mlsanity.com/paper/1806.10176/) (2018)
- [Structural Decompositions of Epistemic Logic Programs](https://mlsanity.com/paper/2001.04219/) (2020)
- [Slightly Superexponential Parameterized Problems](https://mlsanity.com/paper/1902.08723/) (2019)
- [Clique-Width and Directed Width Measures for Answer-Set Programming](https://mlsanity.com/paper/1606.09449/) (2016)
- [Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs](https://mlsanity.com/paper/2108.03022/) (2021)
- [Exploiting Treewidth for Projected Model Counting and its Limits](https://mlsanity.com/paper/1805.05445/) (2018)

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

- [IASCAR: Incremental Answer Set Counting by Anytime Refinement](https://mlsanity.com/paper/2311.07233/) (2023)
- [Current and Future Challenges in Knowledge Representation and Reasoning](https://mlsanity.com/paper/2308.04161/) (2023)
- [Epistemic Logic Programs: Non-Ground and Counting Complexity](https://mlsanity.com/paper/2503.04731/) (2025)
- [Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth?](https://mlsanity.com/paper/2301.07472/) (2023)
- [Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions?](https://mlsanity.com/paper/2402.03539/) (2024)
- [Rejection in Abstract Argumentation: Harder Than Acceptance?](https://mlsanity.com/paper/2408.10683/) (2024)
- [Solving Decision Theory Problems with Probabilistic Answer Set Programming](https://mlsanity.com/paper/2408.11371/) (2024)
- [Counting Answer Sets of Disjunctive Answer Set Programs](https://mlsanity.com/paper/2507.11655/) (2025)

## Abstract (arXiv)

Answer Set Programming (ASP) is a paradigm for modeling and solving problems for knowledge representation and reasoning. There are plenty of results dedicated to studying the hardness of (fragments of) ASP. So far, these studies resulted in characterizations in terms of computational complexity as well as in fine-grained insights presented in form of dichotomy-style results, lower bounds when translating to other formalisms like propositional satisfiability (SAT), and even detailed parameterized complexity landscapes. A generic parameter in parameterized complexity originating from graph theory is the so-called treewidth, which in a sense captures structural density of a program. Recently, there was an increase in the number of treewidth-based solvers related to SAT. While there are translations from (normal) ASP to SAT, no reduction that preserves treewidth or at least keeps track of the treewidth increase is known. In this paper we propose a novel reduction from normal ASP to SAT that is aware of the treewidth, and guarantees that a slight increase of treewidth is indeed sufficient. Further, we show a new result establishing that, when considering treewidth, already the fragment of normal ASP is slightly harder than SAT (under reasonable assumptions in computational complexity). This also confirms that our reduction probably cannot be significantly improved and that the slight increase of treewidth is unavoidable. Finally, we present an empirical study of our novel reduction from normal ASP to SAT, where we compare treewidth upper bounds that are obtained via known decomposition heuristics. Overall, our reduction works better with these heuristics than existing translations.