Tractable answer-set programming with weight constraints: bounded treewidth is not enough

DOI10.1017/S1471068412000099MaRDI QIDQ5410728zbMATH OpenFDO

Authors Reinhard Pichler, Stefan Rümmele, Stefan Szeider, Stefan Woltran

Publication date 17 April 2014

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.3040

zbMATH Keywords

answer-set programmingparameterized complexity analysistreewidth

Mathematics Subject Classification ID

Logic programming (68N17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Cardinality constraints or, more generally, weight constraints are well recognized as an important extension of answer-set programming. Clearly, all common algorithmic tasks related to programs with cardinality or weight constraints - like checking the consistency of a program - are intractable. Many intractable problems in the area of knowledge representation and reasoning have been shown to become linear time tractable if the treewidth of the programs or formulas under consideration is bounded by some constant. The goal of this paper is to apply the notion of treewidth to programs with cardinality or weight constraints and to identify tractable fragments. It will turn out that the straightforward application of treewidth to such class of programs does not suffice to obtain tractability. However, by imposing further restrictions, tractability can be achieved.

Recommendations

• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Nested weight constraints in ASP
• Answer set solving with bounded treewidth revisited
• Treewidth and counting projected answer sets
• Extending and implementing the stable model semantics

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• scientific article; zbMATH DE number 1424025 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Monadic second order logic on graphs with local cardinality constraints
• Safe reduction rules for weighted treewidth
• Safe separators for treewidth
• Treewidth. Computations and approximations

Cited in

(8)

• New width parameters for SAT and \#SAT
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• A multiparametric view on answer set programming
• Treewidth and counting projected answer sets
• Answer set solving with bounded treewidth revisited
• Complexity and approximability of parameterized MAX-CSPs
• Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
• Treewidth in non-ground answer set solving and alliance problems in graphs

This page was built for publication: Tractable answer-set programming with weight constraints: bounded treewidth is not enough

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5410728)