Tractable Abstract Argumentation via Backdoor-Treewidth
DOI:
https://doi.org/10.1609/aaai.v36i5.20501Keywords:
Knowledge Representation And Reasoning (KRR)Abstract
Argumentation frameworks (AFs) are a core formalism in the field of formal argumentation. As most standard computational tasks regarding AFs are hard for the first or second level of the Polynomial Hierarchy, a variety of algorithmic approaches to achieve manageable runtimes have been considered in the past. Among them, the backdoor-approach and the treewidth-approach turned out to yield fixed-parameter tractable fragments. However, many applications yield high parameter values for these methods, often rendering them infeasible in practice. We introduce the backdoor-treewidth approach for abstract argumentation, combining the best of both worlds with a guaranteed parameter value that does not exceed the minimum of the backdoor- and treewidth-parameter. In particular, we formally define backdoor-treewidth and establish fixed-parameter tractability for standard reasoning tasks of abstract argumentation. Moreover, we provide systems to find and exploit backdoors of small width, and conduct systematic experiments evaluating the new parameter.Downloads
Published
2022-06-28
How to Cite
Dvořák, W., Hecher, M., König, M., Schidler, A., Szeider, S., & Woltran, S. (2022). Tractable Abstract Argumentation via Backdoor-Treewidth. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5608-5615. https://doi.org/10.1609/aaai.v36i5.20501
Issue
Section
AAAI Technical Track on Knowledge Representation and Reasoning