Decodyn: Treating Hard Problems with Decomposition and Dynamic Programming

From the very beginning, computers were considered as tools to handle large amount of data (e.g. databases in business domains) or to perform complex reasoning tasks (e.g. planning, expert-systems, diagnosis). But in the world today we face numerous challenging problems which involve the combination of both issues, i.e. complex reasoning over large data. As one example consider social networks such as Facebook which possesses hundreds of millions of users, each of them having friendship relations to other users. A typical reasoning problem over such a structure would be to identify a minimal selection of users such that all users are reached via the friendship relation. Similar situations are apparent in various areas, for instance in medicine, where querying ontologies like SNOMED-CT (which contains 311,000 hierarchically organized concepts) is required or in bio-informatics, where complex structures such as proteins or genomes have to be analyzed. Handling computationally complex queries over huge data is an insurmountable obstacle for standard algorithms, thus novel methods are required. Our solution is to exploit structure. In reality, social networks are not random graphs and medical ontologies are not arbitrary sets of relations. Thus, structural parameters can serve as a key to apply recent techniques from the area of parameterized complexity. We shall focus here on the concept of decomposition (which divides the problem into smaller pieces making use of structural properties of the instance) and dynamic programming algorithms which solve the problem in terms of the decomposed instance. Notably, structure is not solely found in data like social networks but is also present in queries for complex reasoning (for instance, when seeking for a certain structure in molecules, this is naturally reflected in the query). The main vision of the decodyn project is to understand how structure can be simultaneously exploited on these two different levels, in such a way that (deco)mposition and (dyn)amic programming provide novel methods to make problems of this kind amenable to today`s computers. Several query languages which allow formalizations of complex reasoning tasks are nowadays available, among them variants of datalog or description logics. In the course of the project, we will first focus on Answer-Set Programming (also known as disjunctive datalog). In fact, Answer-Set Programming has shown great potential in the aforementioned application areas, but its use is still limited when problems of huge size have to be solved. In the second phase, we intend to migrate our results and methods to other reasoning paradigms and query languages.

From the very beginning, computers were considered as tools to handle large amount of data (e.g. databases in business domains) or to perform complex reasoning tasks (e.g. planning, expert-systems, diagnosis). But in the world today we face numerous challenging problems which involve the combination of both issues, i.e. complex reasoning over large data. As one example consider social networks such as Facebook which possesses hundreds of millions of users, each of them having friendship relations to other users. A typical reasoning problem over such a structure would be to identify a minimal selection of users such that all users are reached via the friendship relation. Handling computationally complex queries over huge data is an insurmountable obstacle for standard algorithms, thus novel methods are required. Our solution is to exploit structure, and in course of the project, we were able to provide methods and solutions which rely on the concepts of decomposition (which divides the problem into smaller pieces making use of structural properties of the instance) and dynamic programming algorithms which solve the problem in terms of the decomposed instance. Among our achieved results are - a new method (decomposition-guided reductions) that allows to pinpoint the parameterized complexity of several problems in a uniform way - development of a software tool for decomposition, which is nowadays used by several research groups - novel implementation methods that make use of (i) advanced storage concepts, (ii) database technology, and (iii) contemporary hardware like GPUs. Our systems were able to handle problem instances of surprising high structural complexity and outperform several state-of-the-art systems in different application domains. Our research has been awarded at different venues, including best paper awards, an early-career award, and prizes for PhD theses.