Algorithms and Theoretical Computer Science

Below we describe four different aspects in which way we attack problems involving algorithms. For many of us, graphs and hypergraphs are the objects we are working with. They consist of a (finite) set of vertices, sometimes also called nodes, and a set of edges. The vertices have labels, say, integer labels, up to , where is the number of vertices; however, in applications each vertex often represents a certain object, for example, a person, building, task, objective or variable.

Edges in graphs are simply a set of two vertices, that is, we think of these two vertices being in relation to each other. It is common to visualize vertices by dots and edges by lines between two vertices; nevertheless, a graph is a priori independent of such a drawing. In hypergraphs we also allow edges of larger size, that is, with three or more vertices. This is usually visualized by a bubble around all vertices in the (hyper)edge.

Edges in graphs can also be directed, that is, have a orientation and point from one vertex to another one, or have weights associated with them.

Graphs are fundamental structures in mathematics. They are very versatile and hence they appear in many contexts. However, although (hyper)graphs are so easy to define, they exhibit very fascinating and partly mysterious behavior that has been subject to very active research in the past decades.

Traditionally, algorithms are designed using simple models of problems and machines. In turn, important results are provable, such as performance guarantees for all possible inputs. This often yields elegant solutions being adaptable to many applications with predictable performance for previously unknown inputs.  In algorithm theory, however, taking up and implementing an algorithm is part of the application development.  Unfortunately, this mode of transferring results is a slow process and sometimes the theoretically best algorithms perform poor in practice.  This causes a growing gap between theory and practice: Realistic hardware with its parallelism, memory hierarchies etc. is diverging from traditional machine models.

In contrast to algorithm theory, algorithm engineering uses an innovation cycle where algorithm design based on realistic models, theoretical analysis, efficient implementation, and careful experimental evaluation using real-world inputs closes gaps between theory and practice and leads to improved application codes and reusable software libraries (see here). This yields results that practitioners can rely on for their specific application.

The algorithm engineering group tackles a broad spectrum of scalable graph algorithms in particular in the context of very large inputs. In general, research is based on five pillars: multilevel algorithms, practical kernelization, parallelization, memetic algorithms and dynamic algorithms that are highly interconnected. To this end, our group engineers algorithms that improve known methods. Typically, we release the techniques and algorithms developed as easy-to-use open source software. Examples include a widely used library of algorithms for (hyper)graph partitioning, graph drawing, (weighted) independent sets, graph clustering, graph generation, minimum cuts, process mapping and many more.

One of the most famous algorithmic problems is the Travelling Salesman problem. Given cities and distances between each pair of cities, what is the shortest tour through all of them? (This can be modelled by a complete graph on vertices with weights on the edges.) Surely, we can simply check all potential routes and choose the shortest one. However, this is not feasible at all! There are roughly such routes, which is a gigantic number even if is only moderately large, say something beyond 20.

Hence, can we do better than that? Yes, but it seems that in general an exponential number in of computation steps are necessary.

Proving that algorithms do not need more than a guaranteed number of steps is known as a worst case analysis. To this end, frequently heavy mathematical theorems are exploited to exhibit structures on graphs that in turn yield improvements on the running time of algorithms.

Our research focus lies on the investigation of graphs and hypergraphs under various viewpoints. This includes questions of the following form:

• When is a particular "simple" graph is subgraph of another graph?
• When do we obtain decompositions of the vertex set or edge set of a graph into another "simple" graph?
• How do typical graphs behave differently in comparison to worst case instances?

Among other results, we solved the famous Oberwolfach problem for large instances, which was posed by Gerhard Ringel in the 1960s.

For most problems there are many different algorithms that solve it and their resource consumption (computation, communication, memory, storage) depends on the problem parameters (data sizes, data arrangement, data types, data values). So already from a theoretic point of view different problem parameters ask for different algorithms, but there are too many algorithms to evaluate them all with respect to resource consumption. Moreover, most algorithms have many different implementations and the execution time of the each implementation depends on the specific hardware. So from a practical point of view it is very difficult to know for given problem parameters and hardware what the best algorithm and implementation are. We can afford to evaluate only very few combinations, because development of good algorithms and implementations are lengthy processes, thus finding the best combination is like looking for a needle in a haystack.

We tackle this challenge by approaching the best combination of algorithm and implementation from the top and bottom. Coming from the bottom means creating algorithmic building blocks with almost optimal performance on specific hardware, i.e. the given computation cannot be performed in significantly less time. Having such building blocks we can quickly assemble algorithms with high performance if the interaction between the blocks is also efficient. In addition, coming from the top we use application guidance into the type of algorithmic structures we need to target. We work mostly with scientific computing applications where the guidance is given by the numerical analysis of the schemes. The building blocks are then parallel data selection and parallel linear algebra operations.

For specific problems we succeed in designing solutions that are almost optimal, resulting in staggering performance on parallel hardware (GPUs, many-core CPUs, FPGAs). However, for most problems such resounding solutions are unknown and even where specific cases are solved more general problem formulations remain a challenge.

We focus on large-scale combinatorial optimization problems with applications in computer vision and bio-informatics. "Combinatorial" means that the solution must be selected from a finite but exponentially growing set, as for example the set of all possible subsets of a given set, permutations or paths in a given graph. Most of such problems can be formulated in a common format of integer linear programs and solved by off-the-shelf software. "Large-scale" means that the size of the problems makes their solution with off-the-shelf methods inefficient or even practically impossible. Indeed, this is often the case in such applications as stereovision and image segmentation, estimation of object rotation and translation in space, as well as cell matching and tracking in microscopic images.

We not only develop dedicated algorithms to optimize given combinatorial problems, but also learn problem parameters from training data. To this end we combine artificial neural networks with the most efficient combinatorial techniques.