Johannes K. Fichte, Martin Kronegger and Stefan Woltran
Multiparametric View on Answer Set Programming
Disjunctive answer set programming (ASP) is one of the fundamental reasoning tasks. Even the consistency problem, i.e., asking whether a given program has an answer set, is on the second level of the polynomial hierarchy. Thus, understanding the computational complexity and in particular the search for tractable fragments is of great importance for the design of efficient algorithms. During the last decades different approaches have been used find such tractable fragments. One such approach is by parameterized complexity theory. However, in the past, the full potential of this approach has not been used since only one or very few parameters have been considered at once.
In this paper, we close this gap by considering several natural parameters for the consistency problem of disjunctive ASP. Therefore, we also take the size of the answer set into account. Such a restriction is particularly interesting for applications that require small solutions. Further, we investigate on the main reasoning problems (brave and skeptical reasoning) of propositional answer set programming also taking the size of the answer sets into account. We show several novel fixed-parameter tractability (fpt) results based on combinations of parameters, XP-membership results and a variety of hardness results (para-NP, W[2], and W[1]-hardness) for the problems mentioned above. Several of these results are obtained by novel reductions to the Weighted Minimal Models Satisfiability problem (WMMSAT).