Preferred Reasoning in ABA by Cycle-Breaking

Nguyen Anh Kiet, Markus UlbrichtIJCAI 2024

Introduction

Assumption-Based Argumentation (ABA) is a prominent framework for non-monotonic reasoning. However, skeptical preferred reasoning in ABA is computationally intensive, often classified as $NP$-hard or $co-NP$-hard. While graph-based properties in Abstract Argumentation (AF) offer "islands of tractability," applying these directly to ABA is challenging. ABA is rule-based, and converting it to an AF can result in an exponential increase in size. This paper investigates whether tractable sub-classes of ABA can be identified directly from its rules and assumptions to enhance reasoning efficiency.

Methodology: The Backdoor Approach

The authors introduce a novel approach using backdoors in a newly defined ABA Dependency Graph ($G_D$). This graph maps the relationships between atoms and their contraries in polynomial time.

Example of an ABA Dependency Graph showing complex relationships between assumptions and rules.

The core strategy involves identifying a "backdoor" set of assumptions ($B$) that, when removed, leaves an acyclic (and thus tractable) dependency graph. The proposed algorithm operates by:

  1. Computing the dependency graph $G_D$.
  2. Identifying a small cycle-breaking backdoor set $B$.
  3. Iterating through possible truth assignments (IN, OUT, or UNDEC) for the backdoor set.
  4. Propagating these assignments through the framework using a "reduct" (partial evaluation) process.

The authors prove that this reasoning problem is Fixed-Parameter Tractable (FPT) relative to the size of the backdoor set. This means if the number of assumptions needed to break all cycles is small, the problem can be solved efficiently regardless of the total size of the knowledge base.

Empirical Evaluation

The algorithm was tested against the ICCMA 2023 competition benchmark, comprising 400 ABA instances, and compared with ASPforABA, the leading solver in the competition's ABA track.

Performance comparison between the Backdoor approach and ASPforABA across different backdoor sizes (k).

The results highlight a specific performance "sweet spot" for the backdoor approach:

  • Small Backdoors ($k \le 5$): The backdoor algorithm significantly outperforms ASPforABA, with an average runtime of 0.17 seconds compared to 1.28 seconds.
  • Medium Backdoors ($k \in [6, 10]$): Both solvers exhibit comparable, high-speed performance.
  • Large Backdoors ($k > 10$): The exponential complexity ($2^k$) becomes a bottleneck, and the general-purpose ASPforABA solver takes the lead.

Conclusion

By bridging rule-based ABA and graph-based AF theory through the dependency graph, the authors provide a practical FPT algorithm for a previously daunting problem. While highly cyclic frameworks remain a challenge, the backdoor method offers a substantial speedup for many real-world instances where cycle-breaking sets are small. Future work aims to extend this to non-flat ABA frameworks and explore alternative backdoor types, such as those breaking only even-length cycles.

Summary updated

BibTeX
@inproceedings{kiet2024preferred,
  author = {Nguyen Anh Kiet and Markus Ulbricht},
  title = {{Preferred Reasoning in ABA by Cycle-Breaking}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure