Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 2827-2834 |
| Seitenumfang | 8 |
| Fachzeitschrift | Proceedings of the AAAI Conference on Artificial Intelligence |
| Jahrgang | 33 |
| Ausgabenummer | 01: AAAI-19, IAAI-19, EAAI-20 |
| Publikationsstatus | Veröffentlicht - 2019 |
| Veranstaltung | 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Annual Conference on Innovative Applications of Artificial Intelligence, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 - Honolulu, USA / Vereinigte Staaten Dauer: 27 Jan. 2019 → 1 Feb. 2019 |
Abstract
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.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Artificial intelligence
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Proceedings of the AAAI Conference on Artificial Intelligence, Jahrgang 33, Nr. 01: AAAI-19, IAAI-19, EAAI-20, 2019, S. 2827-2834.
Publikation: Beitrag in Fachzeitschrift › Konferenzaufsatz in Fachzeitschrift › Forschung › Peer-Review
}
TY - JOUR
T1 - Counting complexity for reasoning in abstract argumentation
AU - Fichte, Johannes Klaus
AU - Hecher, Markus
AU - Meier, Arne
N1 - Funding Information: Funded by Austrian Science Fund FWF grants I2854, Y698, and P30168-N31, as well as the German Research Fund DFG grants HO 1294/11-1 and ME 4279/1-2. The second author is also affiliated with the University of Potsdam, Germany.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85075741804&partnerID=8YFLogxK
U2 - 10.48550/arXiv.1811.11501
DO - 10.48550/arXiv.1811.11501
M3 - Conference article
AN - SCOPUS:85075741804
VL - 33
SP - 2827
EP - 2834
JO - Proceedings of the AAAI Conference on Artificial Intelligence
JF - Proceedings of the AAAI Conference on Artificial Intelligence
SN - 2159-5399
IS - 01: AAAI-19, IAAI-19, EAAI-20
T2 - 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Annual Conference on Innovative Applications of Artificial Intelligence, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019
Y2 - 27 January 2019 through 1 February 2019
ER -