Tractable Abstract Argumentation via Backdoor-Treewidth
Lists
Only you see this
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.
BibTeX
@inproceedings{dvorak2022tractable,
author = {Wolfgang Dvorák and Markus Hecher and Matthias König and André Schidler and Stefan Szeider and Stefan Woltran},
title = {{Tractable Abstract Argumentation via Backdoor-Treewidth}},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2022},
doi = {10.1609/aaai.v36i5.20501},
}Loading related content...