License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.17
URN: urn:nbn:de:0030-drops-85739
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8573/
Go to the corresponding LIPIcs Volume Portal

Fichte, Johannes K. ; Hecher, Markus ; Morak, Michael ; Woltran, Stefan

DynASP2.5: Dynamic Programming on Tree Decompositions in Action

pdf-format:
LIPIcs-IPEC-2017-17.pdf (1 MB)

Abstract

Efficient, exact parameterized algorithms are a vibrant theoretical research area. Recent solving competitions, such as the PACE challenge, show that there is also increasing practical interest in the parameterized algorithms community. An important research question is whether such algorithms can be built to efficiently solve specific problems in practice, that is, to be competitive with established solving systems. In this paper, we consider Answer Set Programming (ASP), a logic-based declarative modeling and problem solving framework. State-of-the-art ASP solvers generally rely on SAT-based algorithms. In addition, DynASP2, an ASP solver that is based on a classical dynamic programming on tree decompositions, has recently been introduced. DynASP2 outperforms modern ASP solvers when the goal is to count the number of solutions of programs that have small treewidth. However, for quickly finding one solutions, DynASP2 proved uncompetitive. In this paper, we present a new algorithm and implementation, called DynASP2.5, that shows competitive behavior compared to state-of-the-art ASP solvers on problems like Steiner tree for low-treewidth graphs, even when the
task is to find just one solution. Our implementation is based on a novel approach that we call multi-pass dynamic programming.

BibTeX - Entry

@InProceedings{fichte_et_al:LIPIcs:2018:8573,
  author =	{Johannes K. Fichte and Markus Hecher and Michael Morak and Stefan Woltran},
  title =	{{DynASP2.5: Dynamic Programming on Tree Decompositions in Action}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8573},
  URN =		{urn:nbn:de:0030-drops-85739},
  doi =		{10.4230/LIPIcs.IPEC.2017.17},
  annote =	{Keywords: Parameterized algorithms, Fixed-parameter linear time, Tree decompositions, Multi-pass dynamic programming}
}

Keywords: Parameterized algorithms, Fixed-parameter linear time, Tree decompositions, Multi-pass dynamic programming
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI