Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation

Authors

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

DOI:

https://doi.org/10.1609/aaai.v30i1.10101

Keywords:

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

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.

Downloads

Published

2016-02-21

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). https://doi.org/10.1609/aaai.v30i1.10101

Issue

Section

Technical Papers: Knowledge Representation and Reasoning