Prof. Dr. Tobias Friedrich

PACE Challenge 2022

MSc Project Seminar - Summer 2022

This course has already started with the maximum of 10 participants, so there is no more room for further enrolements.


As the name suggests, we plan to build a team that takes part in the 2022 PACE-Challenge. This competition is held every year by the Parameterized Algorithms community, and the task is always to create fast algorithms for an NP-hard (usually graph) problem. We are particularly interested in their exact track, where the task is to find an optimum solution - a truly challenging task because of the NP-hardness. The problem of  the 2022 challenge is called Directed Feedback Vertex Set, which asks to find a smallest set of arc deletions that make a given directed graph acyclic; check out the description on the PACE-page here for what is known about this problem and possibly why it is not as easy as it might look at first glance.

This contest is not so much about (fast) coding as it is about developing new algorithmic approaches for a notoriously hard problem. Aiming for exact solutions will require theoretical proof that our solver works correctly. A good PACE-participation is therefore usually followed by a scientific publication about the theoretical properties discovered while working towards the contest. After submitting our solver to the challenge, we will thus work towards publishing our ideas. For you, this means that the second half of the seminar will be spent on writing a scientific report. 

As some observant person detected: The award ceremony of this years PACE-Challenge will be at HPI (since all of ALGO 2022 is), so, let's be victorious hosts! 


There are no formal requirements. Since we aim to take part in the competition with code and corresponding publication, we expect some coding and scientific writing skills. 


The evaluation of the course is based on the performance for the contest and the scientific report detailing the ideas used for the contest. The grade is composed as follows:

  • 50% code for contest
  • 50% report



We will start (and thus finish) this seminar earliy! In order to have a fair chance at the competition, we would like to kick off this project in mid March. We will coordinate the exact time, and also the regular meeting time in general with all participants via moodle. So, if you are interested please register as soon as possible in the moodle course. Registering in moodle does not mean that you are forced to take this seminar, just that you get the information to attend the kick-off to see if this course is interesting for you.