1 Introduction

Graphs are ubiquitous in computing. Treewidth [7] is a parameter that, intuitively, measures how far a graph is from being a tree. This parameter proved to be very useful because many hard problems become tractable if instances are restricted to those whose treewidth is bounded by a constant [6]. Algorithms that exploit this usually employ dynamic programming on a tree decomposition of the instance. A tree decomposition is a tree obtained from a graph, where each node has a bag, which is a set of vertices of the original graph. A decomposition thus divides the instance into several parts. For many problems, we can then apply dynamic programming to compute tables containing partial solutions for the respective subproblems and finally combine them to obtain solutions for the whole problem (if possible).

The D-FLAT system [1, 4] is a tool for rapid prototyping of such algorithms. Users merely need to specify the computation at each node of the tree decomposition in a declarative way, and the system takes care of problem-independent parts like computing a decomposition and combining partial solutions. For formalizing the computations at the decomposition nodes, D-FLAT uses the logic programming language Answer Set Programming (ASP). ASP makes the specification of many combinatorial problems easy, and this often carries over to D-FLAT specifications.

2 Dynamic Programming with D-FLAT

Given an ASP program specified by the user, D-FLAT first reads an input to the problem and generates an appropriate tree decomposition using heuristic methods. It then traverses the decomposition in post-order and executes the user-supplied program at each node (see Fig. 1) with the following information: the vertices in the current bag (current/1), those encountered for the first time (introduced/1), the names of children of the current decomposition node (childNode/1), the (globally unique) identifiers of rows from the tables of these child nodes along with the respective node names (childRow/2), and the contents of these child rows (childItem/2). Output predicate item/1 is used to store the content of the current table row, whereas extend/1 indicates the origins of this row by pointing to one row from each child table.

Fig. 1
figure 1

Procedure at each tree decomposition node

Full size image

We illustrate problem solving in D-FLAT with an example. Consider the D-FLAT encoding from Listing 1, which implements a dynamic programming algorithm for finding independent sets (i.e., sets of vertices such that no two elements are adjacent to each other) in graphs given by facts over the predicate edge.

figure a

In line 1, we guess a row from each child table. By line 2, we never combine child rows that disagree on the status of a bag element. (For this we may assume that each decomposition node with more than one child has the same bag as all children.) If an extended partial solution contains an element that is still present in the current bag, line 3 makes sure that this element still appears in the current row. Line 4 guesses for each introduced bag element whether it is included in the partial solution, and we ensure in line 5 that the partial solution restricted to the current bag is independent.

2.1 Advanced Features

The algorithm formalized in Listing 1 computes a table at each tree decomposition node. However, many dynamic programming algorithms require more involved data structures than this “flat” table structure. Hence D-FLAT supports a generalization where we store a tree of tables at each decomposition node. It has been shown [5] that D-FLAT can thus solve all problems expressible in monadic second-order logic in linear time for instances of bounded treewidth.

D-FLAT also supports optimization problems and allows for anytime optimization; that is, the execution can be interrupted and the best solution found so far is reported [3]. This is realized via lazy evaluation, which essentially fills tables bit by bit. Hereby, D-FLAT does not simply perform one post-order traversal to compute all table rows but tries to compute as few as possible using backtracking in case the currently computed rows do not lead to a solution yet. Moreover, the system provides a facility for shifting arithmetic from ASP encodings into the framework, which often leads to smaller groundings. Finally, there is an extension of D-FLAT that allows for an easy and efficient handling of problems whose solutions are minimal or maximal w.r.t. set inclusion  [2].

3 Sources

Source code and binary releases can be found at https://github.com/bbliem/dflat/. The project website is at http://dbai.tuwien.ac.at/proj/dflat/ and contains references to extensions and related software. For an exhaustive description of D-FLAT, we refer to [4].