Tractable Abstract Argumentation via Backdoor-Treewidth


  • Wolfgang Dvořák TU Wien
  • Markus Hecher TU Wien
  • Matthias König TU Wien
  • André Schidler TU Wien
  • Stefan Szeider TU Wien
  • Stefan Woltran TU Wien



Knowledge Representation And Reasoning (KRR)


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.




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.



AAAI Technical Track on Knowledge Representation and Reasoning