<div class="csl-bib-body">
<div class="csl-entry">Dvořák, W., Hecher, M., König, M., Schidler, A., Szeider, S., & Woltran, S. (2022). Tractable Abstract Argumentation via Backdoor-Treewidth. In <i>Proceedings of the 36th AAAI Conference on Artificial Intelligence</i> (pp. 5608–5615). AAAI Press. https://doi.org/10.1609/aaai.v36i5.20501</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/161632
-
dc.description.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.
en
dc.description.sponsorship
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
-
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartofseries
Proceedings of the ... AAAI Conference on Artificial Intelligence.
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Knowledge Representation and Reasoning
en
dc.subject
Argumentation frameworks
en
dc.subject
backdoor-treewidth approach
en
dc.title
Tractable Abstract Argumentation via Backdoor-Treewidth