Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Hecher, P. Thier, S. Woltran:
"Taming High Treewidth with Abstraction, Nested Dynamic Programming and Database Technology";
Vortrag: SAT 2020 - 23rd International Conference on Theory and Applications of Satisfiability Testing,
Alghero, Italy;
03.07.2020
- 10.07.2020; in: "Theory and Applications of Satisfiability Testing - {SAT} 2020 - 23rd International Conference, Alghero, Italy, July 3-10, 2020, Proceedings",
(2020),
S. 343
- 360.
Kurzfassung englisch:
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.
Zugeordnete Projekte:
Projektleitung Stefan Woltran:
START
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.