Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation


  • Johannes Wallner University of Helsinki
  • Andreas Niskanen University of Helsinki
  • Matti Järvisalo University of Helsinki



abstract argumentation, computational complexity, dynamics of argumentation, extension enforcement, encodings, algorithms


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.




How to Cite

Wallner, J., Niskanen, A., & Järvisalo, M. (2016). Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1).



Technical Papers: Knowledge Representation and Reasoning