Decomposition-Guided Reductions for Argumentation and Treewidth

Johannes Klaus Fichte, Markus Hecher, Yasir Mahmood, Arne MeierIJCAI 2021 · DOI

TL;DR

This paper introduces "decomposition-guided" (DG) reductions to translate argumentation problems into Quantified Boolean Formulas (QBFs) while preserving treewidth. This is crucial because solvers that exploit low treewidth can efficiently handle these QBFs. The authors show that these DG reductions are nearly optimal in terms of treewidth overhead and establish new complexity bounds for logic-based argumentation.

What Problem Does This Paper Address?

Argumentation theory, used for modeling and evaluating arguments, often relies on computational complexity analysis. A key aspect is understanding how the "treewidth" of an instance affects computational difficulty. Treewidth is a graph parameter that indicates how "tree-like" a graph is, and algorithms that exploit low treewidth can be significantly faster. Many argumentation solvers use SAT solvers, which are efficient for low-treewidth instances. However, for this to be truly effective, the reduction from an argumentation problem to a SAT or QBF problem must not introduce a prohibitive treewidth overhead. This paper addresses the question of whether such "treewidth-preserving" reductions exist for argumentation problems, particularly focusing on abstract and logic-based argumentation. For abstract argumentation, it was unknown if treewidth could be preserved linearly, and for logic-based argumentation, even bounded treewidth results were missing.

Methods

The core contribution is the development of Decomposition-Guided (DG) Reductions. These reductions leverage a tree decomposition (TD) of the input graph. A TD breaks down a graph into a tree structure, where each node in the tree (a "bag") contains a subset of the graph's vertices. DG reductions construct a QBF by processing the instance node by node within the TD. The key idea is that the QBF generated for a node t depends not only on the original input at that node (x(t)) but also on the QBFs generated for its children nodes in the TD. This "dynamic programming" approach along the TD allows the treewidth of the resulting QBF to be controlled.

The authors apply this DG reduction framework to various argumentation problems:

  • Abstract Argumentation: They develop DG reductions for computing stable, admissible, semistable, and stage extensions. These reductions translate argumentation problems into SAT or 2-QBF instances while ensuring the treewidth of the resulting formula is linearly related to the treewidth of the original argumentation framework.
  • Logic-Based Argumentation: They tackle argument existence (ARG), argument relevance (ARG-Rel), and argument checking (ARG-Check). For ARG and ARG-Rel, they reduce the problem to 2-QBF using DG reductions. For ARG-Check, which is more complex, they devise a reduction to a set of QBFs with independent quantifiers.

A significant aspect of their work is proving lower bounds under the Exponential Time Hypothesis (ETH). This means they show that, unless P=NP (or a stronger complexity class), their DG reductions cannot be significantly improved in terms of treewidth overhead.

Datasets

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

Key Insights and Ideas

  • Treewidth-Preserving Reductions are Possible: The paper demonstrates that it's possible to reduce complex argumentation problems to QBFs while keeping the treewidth of the resulting formula linearly proportional to the original problem's treewidth. This is a crucial step for making treewidth-aware solvers practical for argumentation.
  • DG Reductions as a General Framework: The concept of Decomposition-Guided reductions provides a systematic way to design treewidth-aware translations, applicable to various argumentation semantics and logic-based problems.
  • Near-Optimal Treewidth Overhead: The ETH-based lower bounds suggest that the linear treewidth increase achieved by DG reductions is likely the best possible, meaning the overhead is fundamentally tied to the problem's inherent complexity.
  • New Complexity Bounds for Logic-Based Argumentation: The paper establishes new upper bounds for logic-based argumentation problems, filling a gap in the understanding of their complexity, especially concerning treewidth.

Key Results

  • Abstract Argumentation: DG reductions are presented for stable, admissible, semistable, and stage extensions, achieving O(k) treewidth overhead, where k is the treewidth of the input. ETH-based lower bounds show this is nearly optimal.
  • Logic-Based Argumentation:
    • ARG and ARG-Rel are reduced to 2-QBF with O(k) treewidth overhead, where k is the treewidth of the input graph. Runtime upper bounds are 2^O(k) * poly(n).
  • ARG-Check is reduced to a set of QBFs, also with O(k) treewidth overhead.
  • Matching ETH-based lower bounds are provided for ARG and ARG-Check, indicating that significant improvements in treewidth are unlikely.
  • Table 1 Summary: The paper provides a comprehensive overview of the established treewidth-awareness and runtime bounds for various argumentation problems, highlighting their new contributions.

Limitations and Future Work

  • Practical Implementation: While the theoretical framework is established, the authors suggest that future work should focus on practical implementation of these DG reductions to verify their robustness and efficiency in real-world scenarios.
  • Stronger ETH: Investigating the implications of stronger versions of the ETH could further highlight the strength of their approach.
  • Other Parameters: The paper raises the question of whether similar treewidth-preserving reductions can be designed for other computational parameters beyond treewidth.
  • Enumeration Complexity: The bijective nature of the reductions suggests potential applicability to enumeration complexity settings, which warrants further rigorous investigation.

Summary updated

BibTeX
@inproceedings{fichte2021decomposition,
  author = {Johannes Klaus Fichte and Markus Hecher and Yasir Mahmood and Arne Meier},
  title = {{Decomposition-Guided Reductions for Argumentation and Treewidth}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/259},
}
Figure