Preferred Reasoning in ABA by Cycle-Breaking

Preferred Reasoning in ABA by Cycle-Breaking

Kiet Nguyen Anh, Markus Ulbricht

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 3523-3531. https://doi.org/10.24963/ijcai.2024/390

We develop a fixed-parameter tractable (FPT) algorithm for skeptical preferred reasoning in assumption-based argumentation (ABA). To this end we make use of so-called backdoors, i.e. sets of assumptions that need to be evaluated s.t. the remaining ABA framework (ABAF) belongs to a computational beneficial sub-class. In order to identify such target classes, we employ a suitable notion of a dependency graph of an ABAF. We show that these graphs can be constructed in polynomial time and that one can efficiently check sufficient properties ensuring that reasoning in the underlying ABAF is tractable. After establishing the theoretical foundations, we test our implementation against the ASPforABA solver which convincingly won the ABA track of the ICCMA'23 competition. As it turns out, our algorithm outperforms ASPforABA on instances with small backdoor sizes.
Keywords:
Knowledge Representation and Reasoning: KRR: Argumentation
Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning