@inproceedings{LehtonenNJ:COMMA2018,
title = {{SAT}-based Approaches to Adjusting, Repairing,
         and Computing Largest Extensions of Argumentation Frameworks},
author = {Tuomo Lehtonen and Andreas Niskanen and Matti J\"arvisalo},
editor = {Sanjay Modgil and Katarzyna Budzynska and John Lawrence},
booktitle = {Proceedings of the 7th International Conference on
             Computational Models of Argument (COMMA 2018)},
volume = {305},
series = {Frontiers in Artificial Intelligence and Applications},
pages = {193--204},
publisher = {IOS Press},
year = {2018},
}

Abstract:

We present a computational study of effectiveness of declarative approaches
for three optimization problems in the realm of abstract argumentation.
In the largest extension problem, the task is to compute a sigma-extension
of largest cardinality (rather than, e.g., a subset-maximal extension) among
the sigma-extensions of a given argumentation framework (AF). The two other
problems considered deal with a form of dynamics in AFs: given a subset S of
arguments of an AF, the task is to compute a closest sigma-extension within
a distance-based setting, either by repairing S into a sigma-extension of
the AF, or by adjusting S to be a sigma-extension containing (or not
containing) a given argument. For each of the problems, we consider both
iterative Boolean satisfiability (SAT) based approaches as well as directly
solving the problems via Boolean optimization using maximum satisfiability
(MaxSAT) solvers. We present results from an extensive empirical evaluation
under several AF semantics sigma using the ICCMA 2017 competition instances
and several state-of-the-art solvers. The results indicate that the choice
of the approach can play a significant role in the ability to solve these
problems, and that a specific MaxSAT approach yields quite generally good
results. Furthermore, with impact on SAT-based AF reasoning systems more
generally, we demonstrate that, especially on dense AFs, taking into account
the local structure of AFs can have a significant positive effect on the
overall solving efficiency.