Counting Complexity for Reasoning in Abstract Argumentation

  • In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. 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 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 (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author details:Johannes Klaus FichteORCiD, Markus Hecher, Arne MeierORCiD
ISBN:978-1-57735-809-1
Title of parent work (English):The Thirty-Third AAAI Conference on Artificial Intelligence, the Thirty-First Innovative Applications of Artificial Intelligence Conference, the Ninth AAAI Symposium on Educational Advances in Artificial Intelligence
Publisher:AAAI Press
Place of publishing:Palo Alto
Publication type:Other
Language:English
Year of first publication:2019
Completion year:2019
Release date:2021/05/04
Page number:8
First page:2827
Last Page:2834
Funding institution:Austrian Science Fund FWFAustrian Science Fund (FWF) [I2854, Y698, P30168-N31]; German Research Fund DFGGerman Research Foundation (DFG) [HO 1294/11-1, ME 4279/1-2]
Organizational units:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science
DDC classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke
Peer review:Referiert