TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 28.11.2013


Page Content

to Navigation

Declarative Problem Solving on Tree Decompositions

Dipl.-Ing. Michael Abseher, M.Sc. Bernhard Bliem (TU Vienna)

Many intractable problems become tractable when the treewidth of the instances under consideration is bounded by a constant. One possibility to exploit bounded treewidth is to formulate a dynamic programming algorithm on the instance's tree decompositions. Until now, implementing such algorithms, however, has usually been quite intricate which is due to the lack of supporting tools that offer an adequate language for conveniently specifying such algorithms. We therefore present a method for problem solving that enables the user to specify such algorithms in a declarative way. For this, we employ Answer Set Programming together with a software framework that makes rapid prototyping of algorithms on tree decompositions possible. We illustrate the versatility of the approach by applying it to a selection of different problems. It can be shown that this method is powerful enough to solve all problems parameterized by treewidth in FPT time if they are expressible in monadic second-order logic.

28.11.2013 16:15
Michael Abseher, Bernhard Bliem
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe