Tractable Abstract Argumentation via Backdoor-Treewidth
Keywords:Knowledge Representation And Reasoning (KRR)
AbstractArgumentation 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.
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
AAAI Technical Track on Knowledge Representation and Reasoning