Research topics and projects

The design and analysis of exact algorithms constitutes the main research field of the Theory Group. One of our central interests lies in investigating the parameterized complexity of hard problems.

We are currently involved in two projects supported by the Deutsche Forschungsgemeinschaft (DFG):

Pragmatic Parameterized Algorithms

Pragmatische Parametrisierte Algorithmen, RO 927/12-1

Our goal is to develop efficient algorithms that are (1) easily translatable into programs and run successfully under real-world constraints; and, (2) competitive with or even faster than the current best algorithms in their asymptotic behavior. The constraints we have in mind include implementation time, space requirements and running time guarantees. It follows therefore that techniques commonly used to obtain running-time gains in theoretical algorithms, such as complex meta-theorems, exponential space and exponential speed-ups at the cost of high polynomial factors cannot be used directly. By providing transparent time and space bounds, i.e., by keeping polynomial and constants factors within reasonable limits, we wish to push the envelope of algorithms that can be successfully engineered for use in industry and applications.

Theoretical and practical aspects of kernelization

Effiziente Vorverarbeitungsalgorithmen, Kernels und Parametrisierte Komplexitätstheorie, RO 927/12-1

Kernelization is an area of parameterized complexity that deals with the study of preprocessing algorithms. A kernelization algorithm essentially strips away the easy parts of a problem instance exposing the core or the kernel. This is an area that has attracted the attention of both theoreticians and practitioners for the interesting mathematical problems it poses and the practical utility of many of the solutions. The objective of this project is to study both theoretical and practical aspects of kernelization algorithms. On the theoretical side, we plan to investigate topics such as kernelization using non-standard parameters where some structural aspect of the input (other than the solution size) is used as parameter. Other topics include strong polynomial kernels, Turing kernels, and the connection between kernelization and approximability. On the practical side, we plan to design kernelization algorithms for concrete problems with the aim of implementing these algorithms. In particular, we want to investigate the possibility of improving kernels for several problems on planar graphs (among others).

Decision and optimization problems for graphs with a given tree decomposition

Entscheidungs- und Optimierungsprobleme für Graphen mit gegebender Baumzerlegung, RO 927/12-1

Past projects

The following is a list of past DFG-supported projects.

Structural Graph Theory & Parameterized Complexity

Strukturelle Graphtheorie und parametrisierte Komplexität, RO 927/9-1

Many real-world algorithmic problems turn out to be intractable in their full generality. Parameterized complexity, however, provides a useful framework for a refined analysis of such hard problems, and a new concept in designing algorithms that can solve hard problems for real-world instances efficiently. In contrast to heuristics, this approach provides guaranteed runtime bounds. Graphs are combinatorial structures suitable for modeling many discrete decision and optimization problems. Structural graph theory has already proven very useful in parameterized algorithmics. For instance, most of the traditional hard problems are efficiently solvable on graphs of bounded tree-width. We plan to exploit further structural properties of graphs like branch-width, DAG-width, rank-width, or their topological properties. Our goal is to find new application areas of structural graph theory in parameterized algorithm design through collaboration of our research groups from both areas.

TAPI

Theoretische Algorithmen auf Praktischen Instanzen, RO 927/6

The TAPI project focuses on a refined analysis of running times using appropriate structural properties - rather than just the size - of the input. In many cases, this approach allows for a better understanding of the computational hardness that is inherent to the problem at hand. This consequently leads to the design of new algorithms that usually outperform previous algorithms on at least an entire class of interesting instances, if not in all cases.

Intuitive algorithms

Intuitive Algorithmen, RO 927/7

This project is about intuitive algorithms It is a common phenomenon that algorithms are made more and more complex in order to ease the derivation of better and better runtime bounds. In this project, however, we aim at designing very simple, intuitive algorithms at the expense of a more difficult analysis. Of course, it takes new ideas and techniques in order to prove good runtime bounds for these nice (easy to comprehend, easy to implement, easy to verify) algorithms. In many cases, this entails proving better worst-case bounds for hitherto heuristic methods.