K. Nguyen Anh, and M. Ulbricht. Proceedings of the Thirty-ThirdInternational Joint Conference on Artificial Intelligence, California, International Joint Conferences on Artificial Intelligence Organization, (August 2024)
Abstract
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.
%0 Conference Paper
%1 Nguyen_Anh2024-bc
%A Nguyen Anh, Kiet
%A Ulbricht, Markus
%B Proceedings of the Thirty-ThirdInternational Joint Conference on Artificial Intelligence
%C California
%D 2024
%I International Joint Conferences on Artificial Intelligence Organization
%K topic_knowledge
%T Preferred reasoning in ABA by cycle-breaking
%X 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.
@inproceedings{Nguyen_Anh2024-bc,
abstract = {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.},
added-at = {2024-09-10T10:41:24.000+0200},
address = {California},
author = {Nguyen Anh, Kiet and Ulbricht, Markus},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/286553fb98d7f11443fd58510a0cb8067/scadsfct},
booktitle = {Proceedings of the {Thirty-ThirdInternational} Joint Conference on Artificial Intelligence},
conference = {Thirty-Third International Joint Conference on Artificial Intelligence \{IJCAI-24\}},
interhash = {9b758f8b6acf3b89ad8cbfb08a17df53},
intrahash = {86553fb98d7f11443fd58510a0cb8067},
keywords = {topic_knowledge},
location = {Jeju, South Korea},
month = aug,
publisher = {International Joint Conferences on Artificial Intelligence Organization},
timestamp = {2024-11-22T15:46:07.000+0100},
title = {Preferred reasoning in {ABA} by cycle-breaking},
year = 2024
}
