@inproceedings{OikarinenJ:JELIA2014,
 author = {Emilia Oikarinen and Matti J\"arvisalo},
 title  = {Answer Set Solver Backdoors},
 editor = {Eduardo Ferme and Joao Leite},
 booktitle = {Proceedings of the 14th European Conference on Logics 
              in Artificial Intelligence (JELIA 2014)},
 publisher = {Springer},
 series = {Lecture Notes in Artificial Intelligence},
 OPTvolume = {8761},
 OPTpages  = {674-683},
 year   = {2014},
}

Abstract:

The concept of backdoor variables offers a generic notion for providing 
insights to the surprising success of constraint satisfaction solvers in 
solving remarkably complex real-world instances of combinatorial problems. 
We study backdoors in the context of answer set programming (ASP), and 
focus on studying the relative size of backdoors in terms of different 
state-of-the-art answer set solving algorithms. We show separations of the 
ASP solver families in terms of the smallest existing backdoor sets for 
the solvers.