# Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 55 references that are in the map.
- First posted on arXiv 23 Feb 2021.

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

- [Counting Complexity for Reasoning in Abstract Argumentation](https://mlsanity.com/paper/1811.11501/) (2018)
- [Paradigms for Parameterized Enumeration](https://mlsanity.com/paper/1306.2171/) (2013)
- [Parameterised Complexity of Abduction in Schaefer's Framework](https://mlsanity.com/paper/1906.00703/) (2019)

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

- [Diversity of Extensions in Abstract Argumentation](https://mlsanity.com/paper/2605.13332/) (2026)
- [Representative Sets in Propositional Abduction](https://mlsanity.com/paper/2607.21183/) (2026)

## Abstract (arXiv)

Logic-based argumentation is a well-established formalism modelling nonmonotonic reasoning. It has been playing a major role in AI for decades, now. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this paper, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Parson et al., J. Log. Comput., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: first, we consider all possible propositional fragments of the problem within Schaefer's framework (STOC 1978), and then study different parameterizations for each of the fragment. We identify a list of reasonable structural parameters (size of the claim, support, knowledge-base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (paraNP and beyond).