[Back]

M. Hecher:
"Answer Set Solving exploiting Treewidth and its Limits";
Talk: The 25th International Conference on Principles and Practice of Constraint Programming, Stamford, USA; 2019-09-30 - 2019-10-04; in: "CP 2019", (2019), 1 - 7.

Parameterized algorithms have been subject to extensive research
of recent years and allow to solve hard problems by exploiting
a parameter of the corresponding problem instances. There, one goal
is to devise algorithms, where the runtime is exponential exclusively
in this parameter. One particular well-studied structural parameter is
treewidth. Typically, a parameterized algorithm utilizing treewidth takes
or computes a tree decomposition, which is an arrangement of a graph
into a tree, and evaluates the problem in parts by dynamic programming
on the tree decomposition. In our research, we want to exploit treewidth
in the context of Answer Set Programming (ASP), a declarative modeling
and solving framework, which has been successfully applied in several
application domains and industries for years. So far, we presented algorithms
for ASP for the full ASP-Core-2 syntax, which is competitive
especially when it comes to counting answer sets. Since dynamic programming
on tree decomposition lands itself well to counting, we designed a
framework for projected model counting, which applies to ASP, abstract
argumentation and even to problems higher in the polynomial hierarchy.
Given standard assumptions in computational complexity, we established
a novel methodology for showing lower bounds, and we showed that most
worst-case runtimes of our algorithms cannot be signi cantly improved.

Project Head Stefan Woltran:
START