As the name suggests, we plan to build a team that takes part in the 2023 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. The problem of the 2023 challenge is to compute the twinwidth of a graph, a graph-width parameter that has been studied prominently in the recent times. The challenge consists of an Exact track as well as a heuristic track, that will be ranked seperately.
The PACE contest is not so much about (fast) coding as it is about developing new algorithmic approaches for a notoriously hard problem over many months. 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.
The submission of the final code is in June 2023. So we plan to offer a second project seminar in Summer Semester 2023 as a continuation of this one. However, it does not mean that you have to join the course next semester. You are free to leave the team after one semester.
The initial few weeks of the current course will be about reading the results about twinwidth and presenting them for the whole team. Then, by December we will aim to start with our first implemenation for the challenge. At the end of the semester you will be required to submit a writeup describing the current state of the implementation(s), the bottlenecks faced, and potential further ideas to strengthen the implementation(s).
We were successfull in last year's PACE challenge (PACE 2022) by securing third place in the exact track, so let us continue the tradition.