Personen: Prof. Dr. Tobias Friedrich, Dr. Katrin Casel, Dr. Sarel Cohen, Maximilian Katzmann, Gregor Lagodzinski, Martin Schirneck
Links: Courses IT-Systems Engineering, Algorithm Engineering Moodle

In many algorithms used in computing environments such as massive storage devices, large scale parallel computation, and communication networks, recovering from failures must be an integral part. Therefore, designing algorithms and data-structures whose running time is efficient even in the presence of failures is an important task. In this project seminar we study two research directions: (1) variants of shortest paths algorithms and data-structures in settings with failures, and (2) fault-tolerant in the settings of fixed parameter tractable (FPT) algorithms. See more details on these problems below.

The goal is to learn and practice important research techniques: literature search, understanding and presenting research papers, developing ideas in the group, testing of conjectures with the computer, writing down results.

The main focus of the project seminar lies on active research. You will form small groups to work on the topic of your choice. For each topic, there will be a short introduction in the first few weeks. During this time you will get familiar with the underlying problem. After that, you will actively work out solutions for the problem. We will support you with weekly meetings where we discuss your ideas and approaches, the progress, and further actions. While you will be guided by us, we encourage you to propose your own ideas. In the end, each team will write up their findings in a paper and present their results to the others. Summing up, the outline of the course looks roughly as follows.

• First half: Introduction to the topic, literature review, each student presents an existing paper from a list of relevant papers.
• Second half: confrontation with the topic and active research on it. Conducting research together with the lecturers on these problems. Writing a paper and presenting your results.

There are no formal requirements to participate in this course. However, the students should be familiar with algorithms and data-structures.

The grade will be based on 70% on your scientific report / paper and 30% on your presentations (of both an existing paper, and of your new results).

There will be an introductory meeting via Zoom in the first week of the lecture period (details will follow). There, we will discuss the topics, the teams, details and all the following dates.

We will research variants of shortest paths algorithms and data-structures in setting with failures as well as fixed-parameter tractable algorithms in settings with failures, as described below.

(1) We study variants of shortest paths algorithms and data-structures in setting with failures. In particular, we study the Replacement Paths Problem (RP), where given a graph G with n vertices and m edges and let P be a shortest path  from s to t in G the replacement paths problem is to compute for every edge e in P the shortest path from s to t avoiding e.

The goal of this research direction is to construct efficient algorithm and data-structures for computing both exact and approximate replacement paths in various settings, and derandomize existing optimal randomized algorithms for these problems.

(2) Fault-Tolerant Fixed Parameter Tractable Algorithms – the goal in this research direction is to develop efficient algorithms and data-structures to solve fixed-parameter tractable algorithms (such as k-path, vertex cover, maximum independent set, etc.) in settings with failures. Upon a failure, it is inefficient to re-compute in exponential time the solution to the fixed-parameter tractable problem. Instead to goal is preprocess the graph in exponential time, and then upon failure to compute the solution in polynomial or even poly-logarithmic time.

Here are some references for examples:

Shortest Paths Problems:

[1] (1+epsilon)-Approximate f-Sensitive Distance Oracles, by Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan, published in SODA 2017.