[Back]

S. Woltran:
"Dynamic Programming on Tree Decompositions in Practice";
Keynote Lecture: 8th European Starting AI Researcher Symposium, Den Haag (invited); 2016-08-29 - 2016-08-30.

Many problems in Artificial Intelligence are known to be NP-hard.
A recent approach to deal with intractability comes from
parameterized complexity, which makes it possible to identify
instances that can be solved efficiently due to inherent
structural features. One prominent parameter to capture structure
is treewidth, which is defined in terms of tree decompositions.

To put such theoretical tractability results into practice,
dynamic programming (DP) during a traversal of a tree
decomposition is the standard technique. However, the concrete
implementation of suitable efficient algorithms is often tedious.
Therefore we have developed a family of systems that allow the
user to specify the DP algorithm in a declarative fashion and
where the computation of intermediate solutions is delegated to a
logic-programming system.

In this talk, we first give a brief introduction to our core
system, called D-FLAT, and demonstrate its usage on some standard
DP algorithms. In the second part of the talk, we reflect on some
recent developments, including improvements in tree-decomposition
heuristics, space-efficient storage, and a lazy variant of DP that
makes use of modern Answer-Set Programming technology.

Project Head Stefan Woltran:
START