[Back]

M. Hecher, P. Thier, S. Woltran:
"Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology";
Talk: DPSW 2020 - Declarative Problem Solving Workshop, Santiago de Compostela, Spain; 2020-08-29 - 2020-08-30.

Treewidth is one of the most prominent structural parameters.
While numerous theoretical results establish tractability under the
assumption of fixed treewidth, the practical success of exploiting this
parameter is far behind what theoretical runtime bounds have promised.
In particular, a naive application of dynamic programming (DP) on tree
decompositions (TDs) suffers already from instances of medium width.
In this paper, we present several measures to advance this paradigm
towards general applicability in practice: We present nested DP, where
different levels of abstractions are used to (recursively) compute TDs
of a given instance. Further, we integrate the concept of hybrid solving,
where subproblems hidden by the abstraction are solved by classical
search-based solvers, which leads to an interleaving of parameterized and classical solving. Finally, we provide nested DP algorithms and implementations relying on database technology for variants and extensions of
Boolean satisfiability. Experiments indicate that the advancements are
promising.

Project Head Stefan Woltran:
HYPAR

Project Head Stefan Woltran:
START