@inproceedings{PrevitiJ:SAC2018,
title = {A Preference-Based Approach to Backbone Computation
         with Application to Argumentation},
author = {Alessandro Previti and Matti J\"arvisalo},
editor = {Hisham M. Haddad and Roger L. Wainwright and Richard Chbeir},
booktitle = {Proceedings of the 33rd ACM/SIGAPP Symposium on Applied Computing (SAC 2018)},
pages = {896--902},
publisher = {ACM},
year = {2018},
}

Abstract:

The backbone of a constraint satisfaction problem consists of those variables
that take the same value in all solutions. Algorithms for determining the
backbone of propositional formulas, i.e., Boolean satisfiability (SAT)
instances, find various real-world applications. From the knowledge
representation and reasoning (KRR) perspective, one interesting connection is
that of backbones and the so-called ideal semantics in abstract argumentation.
In this paper, we propose a new backbone algorithm which makes use of a
"SAT with preferences" solver, i.e., a SAT solver which is guaranteed to output
a most preferred satisfying assignment w.r.t. a given preference over literals
of the SAT instance at hand. We also show empirically that the proposed approach
is specifically effective in computing the ideal semantics of argumentation
frameworks, noticeably outperforming an other state-of-the-art backbone solver
as well as the winning approach of the recent ICCMA 2017 argumentation solver
competition in the ideal semantics track.