Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation
Abstract
Understanding the dynamics of argumentation frameworks (AFs) is important in the study of argumentation in AI. In this work, we focus on the so-called extension enforcement problem in abstract argumentation. We provide a nearly complete computational complexity map of fixed-argument extension enforcement under various major AF semantics, with results ranging from polynomial-time algorithms to completeness for the second-level of the polynomial hierarchy. Complementing the complexity results, we propose algorithms for NP-hard extension enforcement based on constrained optimization. Going beyond NP, we propose novel counterexample-guided abstraction refinement procedures for the second-level complete problems and present empirical results on a prototype system constituting the first approach to extension enforcement in its generality.
Cite
Text
Wallner et al. "Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10101Markdown
[Wallner et al. "Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/wallner2016aaai-complexity/) doi:10.1609/AAAI.V30I1.10101BibTeX
@inproceedings{wallner2016aaai-complexity,
title = {{Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation}},
author = {Wallner, Johannes Peter and Niskanen, Andreas and Järvisalo, Matti},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {1088-1094},
doi = {10.1609/AAAI.V30I1.10101},
url = {https://mlanthology.org/aaai/2016/wallner2016aaai-complexity/}
}