Answer Set Solver Backdoors

Abstract. The concept of backdoor variables offers a generic notion for provid-ing 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 study-ing 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.