TY - GEN
T1 - A Multiparametric View on Answer Set Programming
AU - Fichte, Johannes Klaus
AU - Kronegger, Martin
AU - Woltran, Stefan
PY - 2017/7
Y1 - 2017/7
N2 - Disjunctive answer set programming (ASP) is an important
framework for declarative modeling and problem solving, where the computational
complexity of basic decision problems like consistency (deciding
whether a program has an answer set) is located on the second level of
the polynomial hierarchy. During the last decades different approaches
have been applied to find tractable fragments of programs, in particular,
also using parameterized complexity. However, the full potential of
parameterized complexity has not been unlocked since only one or very
few parameters have been considered at once. In this paper, we consider
several natural parameters for the consistency problem of disjunctive
ASP. In addition, we also take the size of the answer set into account; a
restriction that is particularly interesting for applications requiring small
solutions. Previous work on parameterizing the consistency problem by
the size of answer sets yielded mostly negative results. In contrast, we
start from recent findings for the problem WMMSAT and show several
novel fixed-parameter tractability (fpt) results based on combinations of
parameters. Moreover, we establish a variety of hardness results (paraNP,
W[2], and W[1]-hardness) to assess tightness of our combined parameters.
AB - Disjunctive answer set programming (ASP) is an important
framework for declarative modeling and problem solving, where the computational
complexity of basic decision problems like consistency (deciding
whether a program has an answer set) is located on the second level of
the polynomial hierarchy. During the last decades different approaches
have been applied to find tractable fragments of programs, in particular,
also using parameterized complexity. However, the full potential of
parameterized complexity has not been unlocked since only one or very
few parameters have been considered at once. In this paper, we consider
several natural parameters for the consistency problem of disjunctive
ASP. In addition, we also take the size of the answer set into account; a
restriction that is particularly interesting for applications requiring small
solutions. Previous work on parameterizing the consistency problem by
the size of answer sets yielded mostly negative results. In contrast, we
start from recent findings for the problem WMMSAT and show several
novel fixed-parameter tractability (fpt) results based on combinations of
parameters. Moreover, we establish a variety of hardness results (paraNP,
W[2], and W[1]-hardness) to assess tightness of our combined parameters.
M3 - Conference proceedings
VL - 1868
T3 - CEUR Workshop Proceedings
BT - Proceedings of the 10th Workshop on Answer Set Programming and Other Computing Paradigms co-located with the 14th International Conference on Logic Programming and Nonmonotonic Reasoning, ASPOCP@LPNMR
A2 - Bart Bogaerts , Amelia Harrison, null
PB - CEUR
ER -