Counting Complexity for Reasoning in Abstract Argumentation

verfasst von: Johannes Klaus Fichte, Markus Hecher, Arne Meier
Abstract: In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics, including credulous reasoning. When asking for projected counts, we are interested in counting the number of extensions of a given argumentation framework, while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by the treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming. Our algorithms run in double or triple exponential time in the treewidth, depending on the semantics under consideration. Finally, we establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension under the exponential time hypothesis (ETH).
Organisationseinheit(en): Institut für Theoretische Informatik
Externe Organisation(en): Linkoping University
Massachusetts Institute of Technology (MIT)
Typ: Artikel
Journal: Journal of Artificial Intelligence Research
Band: 80
Seiten: 805–834
Anzahl der Seiten: 30
ISSN: 1076-9757
Publikationsdatum: 23.06.2024
Publikationsstatus: Veröffentlicht
Peer-reviewed: Ja
ASJC Scopus Sachgebiete: Artificial intelligence
Elektronische Version(en): https://doi.org/10.1613/jair.1.16210 (Zugang: Offen)

BibTeX

@article{179bda9fddc24fea8329af4e57676bc7,
title = "Counting Complexity for Reasoning in Abstract Argumentation",
abstract = "In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics, including credulous reasoning. When asking for projected counts, we are interested in counting the number of extensions of a given argumentation framework, while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by the treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming. Our algorithms run in double or triple exponential time in the treewidth, depending on the semantics under consideration. Finally, we establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension under the exponential time hypothesis (ETH).",
author = "Fichte, {Johannes Klaus} and Markus Hecher and Arne Meier",
note = "Publisher Copyright: {\textcopyright}2024 The Authors.",
year = "2024",
month = jun,
day = "23",
doi = "10.1613/jair.1.16210",
language = "English",
volume = "80",
pages = "805–834",
journal = "Journal of Artificial Intelligence Research",
issn = "1076-9757",
publisher = "Morgan Kaufmann Publishers, Inc.",
}