Clique-width and directed width measures for answer-set programming

DOI10.3233/978-1-61499-672-9-1105zbMATH Open1403.68029arXiv1606.09449OpenAlexW2962927332MaRDI QIDQ4576239FDOQ4576239

Authors: Bernhard Bliem, Sebastian Ordyniak, Stefan Woltran 

Publication date: 12 July 2018

Abstract: Disjunctive Answer Set Programming (ASP) is a powerful declarative programming paradigm whose main decision problems are located on the second level of the polynomial hierarchy. Identifying tractable fragments and developing efficient algorithms for such fragments are thus important objectives in order to complement the sophisticated ASP systems available to date. Hard problems can become tractable if some problem parameter is bounded by a fixed constant; such problems are then called fixed-parameter tractable (FPT). While several FPT results for ASP exist, parameters that relate to directed or signed graphs representing the program at hand have been neglected so far. In this paper, we first give some negative observations showing that directed width measures on the dependency graph of a program do not lead to FPT results. We then consider the graph parameter of signed clique-width and present a novel dynamic programming algorithm that is FPT w.r.t. this parameter. Clique-width is more general than the well-known treewidth, and, to the best of our knowledge, ours is the first FPT algorithm for bounded clique-width for reasoning problems beyond SAT.

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

Recommendations

• A multiparametric view on answer set programming
• Answer set solving with bounded treewidth revisited
• Backdoors to tractable answer set programming
• The impact of treewidth on grounding and solving of answer set programs
• Treewidth in non-ground answer set solving and alliance problems in graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Logic programming (68N17)

Cited In (5)

• Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs
• A multiparametric view on answer set programming
• Title not available (Why is that?)
• Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
• Inductive computations on graphs defined by clique-width expressions

This page was built for publication: Clique-width and directed width measures for answer-set programming

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