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 team has already made some progress in ideas and implementation of the solver for the Exact track during the previous semester. However, there are still many challenges to overcome in order for the solver to be competitive. The submission of the final code for the competition is due on June 1st. There is also a requirement to submit the solver description, in the form of a scientific manuscript, with the deadline on June 15th. Thus, the workload for the course will be largely concentrated before these deadlines.
On the first few meetings we will introduce the problem and the current state of our solver, and distribute the tasks regarding further experiments and subroutines to implement. Then we will have weekly meetings to update on the progress and synchronize the efforts.
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.
