On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks

Markus Kröll, Reinhard Pichler, Stefan WoltranIJCAI 2017 · DOI

TL;DR

This paper tackles the problem of enumerating all possible coherent sets of arguments (extensions) in abstract argumentation frameworks (AFs), a problem that has been largely overlooked compared to decision problems like checking if an argument is accepted. The authors provide a comprehensive complexity analysis for enumerating extensions under 11 different semantics, considering various structural restrictions on AFs, and offering a clear map of tractable vs. intractable scenarios.

What Problem Does This Paper Address?

Abstract argumentation frameworks (AFs) are a powerful tool for modeling reasoning and decision-making, representing arguments and their conflicts as a directed graph. Different "semantics" define what constitutes a valid, coherent set of arguments (an "extension") that can survive these conflicts. While many computational problems related to AFs, such as determining if an argument is skeptically or credulously accepted, have been extensively studied and often found to be computationally hard (requiring NP-complete or worse solutions), the problem of enumerating all possible extensions has received much less attention. This is a critical gap because practical argumentation systems often need to present users with all valid lines of reasoning, not just confirm the existence of one. The authors aim to fill this gap by systematically analyzing the computational complexity of enumerating extensions for a wide range of semantics and under common structural restrictions on AFs.

Methods

The paper's core contribution lies in its complexity analysis. The authors leverage established complexity classes for enumeration problems, specifically DelayP (where each solution is output with polynomial delay) and OutputP (where the total time to output all solutions is polynomial in the input size plus the number of solutions). They also introduce DelayPp, which requires polynomial delay and polynomial space, a more practical notion of tractability.

Their methodology involves:

  • Defining Enumeration Problems: Formalizing the enumeration problem for each semantics as a pair (L, Sol), where L is a language and Sol is a function mapping inputs to sets of solutions.
  • Complexity Classes: Utilizing DelayP, OutputP, and DelayPp to classify the tractability of these enumeration problems.
  • Structural Restrictions: Analyzing AFs under common restrictions like bipartite, symmetric (with and without irreflexivity), and no-even-cycle graphs. These restrictions are known to simplify decision problems and are investigated here for their impact on enumeration.
  • Proof Techniques: Employing reductions from known hard problems (like SAT) and leveraging existing results on decision problems (e.g., ManySol problem, which checks if there are at least m solutions) to prove intractability. They also use constructive algorithms and lemmas (like Lemma 1 for enumerating admissible sets) to establish tractability.
  • Table-Based Summary: Presenting their findings in a comprehensive table that maps each of the 11 semantics against the 5 classes of AFs, clearly indicating tractable (DelayP, DelayPp, trivial) and intractable (not in OutputP) cases.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Enumeration is Harder (or Different): The paper highlights that the complexity of enumerating extensions can differ significantly from that of related decision problems. For instance, while skeptical and credulous reasoning for cf2 semantics are intractable, enumerating cf2 extensions is surprisingly tractable (DelayPp). This suggests that focusing solely on decision problems might miss important computational nuances.
  • Structural Restrictions Matter: The study demonstrates how specific structural properties of AFs can dramatically reduce the complexity of enumeration. For example, symmetric AFs lead to collapses in semantics (e.g., cf and adm become equivalent), simplifying enumeration.
  • A Complete Landscape: The paper provides a remarkably complete picture of the enumeration complexity for a broad set of semantics and common AF restrictions, offering a valuable resource for understanding the computational landscape.
  • Tractability vs. Practicality: The distinction between DelayP and DelayPp is crucial. While a problem might be theoretically solvable with polynomial delay (DelayP), it might require exponential space, making it impractical. The authors explicitly identify cases where DelayPp holds, indicating more practical tractability.

Key Results

The paper provides a detailed complexity classification for enumerating extensions under 11 semantics across 5 classes of AFs (unrestricted, bipartite, symmetric, irreflexive-symmetric, no-even-cycles). The main results are summarized in Table 2, which shows:

  • Tractable Cases: Many semantics, especially for simpler ones like cf and naive, are tractable (DelayPp) even for unrestricted AFs. Tractability often carries over to restricted cases.
  • Intractable Cases: Several semantics, particularly stable, stage, semi, and stage2, remain intractable (not in OutputP unless P=NP) for unrestricted AFs and even for some restricted classes like bipartite AFs.
  • "Trivial" Cases: For certain semantics and restrictions (e.g., comp on no-even-cycle AFs), the number of extensions is at most one, making enumeration trivial.
  • Specific Findings:
    • cf and naive extensions are enumerable in DelayPp for unrestricted AFs.
  • cf2 extensions are enumerable in DelayPp for unrestricted AFs.
  • adm extensions are intractable (not OutputP) for unrestricted AFs.
  • stable, stage, semi, and stage2 extensions are intractable for bipartite AFs.
  • stable, stage, semi, and stage2 extensions are intractable for symmetric AFs.
  • stage and stage2 extensions are intractable for no-even-cycle AFs.

Limitations and Future Work

  • Unexplored Restrictions: The authors acknowledge that many other structural restrictions on AFs exist (e.g., AFs with no odd cycles, bounded treewidth) that could be investigated. They note that for AFs with no odd cycles, their results for bipartite AFs largely carry over.
  • Adm Semantics on No-Even-Cycle AFs: The complexity of enumerating adm extensions for AFs with no even cycles remains an open question.
  • Practical Implementations: While the paper provides theoretical complexity bounds, the practical performance of algorithms for DelayPp enumeration, especially concerning space complexity, is not empirically evaluated.
  • Beyond Standard Semantics: The study focuses on a specific set of 11 semantics. Future work could extend this analysis to other less common but potentially important semantics.
  • Meta-Theorems and Tool Development: The authors suggest that their findings can guide developers of argumentation tools, particularly those using reduction-based approaches, to ensure efficient computation for tractable cases. They also highlight the potential for using meta-theorems for further analysis on restricted graph classes.

Summary updated

BibTeX
@inproceedings{kroll2017complexity,
  author = {Markus Kröll and Reinhard Pichler and Stefan Woltran},
  title = {{On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/159},
}
Figure