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!
