Tractable Abstract Argumentation via Backdoor-Treewidth
Wolfgang Dvořak, Markus Hecher, Matthias König, André Schidler, Stefan Szeider, Stefan Woltran
[AAAI-22] Main Track
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 present the results of systematic experiments evaluating the new parameter.
Introduction Video
Sessions where this paper appears
-
Poster Session 3
Fri, February 25 8:45 AM - 10:30 AM (+00:00)
Blue 5
-
Poster Session 7
Sat, February 26 4:45 PM - 6:30 PM (+00:00)
Blue 5
-
Oral Session 7
Sat, February 26 6:30 PM - 7:45 PM (+00:00)
Blue 5