# Counting Complexity for Reasoning in Abstract Argumentation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2018.

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

- [Facets in Argumentation: A Formal Approach to Argument Significance](https://mlsanity.com/paper/2505.10982/) (2025)
- [Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework](https://mlsanity.com/paper/2102.11782/) (2021)
- [Abstract Dialectical Frameworks are Boolean Networks (full version)](https://mlsanity.com/paper/2407.02055/) (2024)
- [Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach](https://mlsanity.com/paper/2407.05058/) (2024)
- [Diversity of Extensions in Abstract Argumentation](https://mlsanity.com/paper/2605.13332/) (2026)

## Abstract (arXiv)

In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a given argumentation framework while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.