Prof. Dr. Tobias Friedrich

PACE challenge on Twinwidth

MSc Project Seminar - Summer 2023

This course admits a maximum of 10 participants. So, if you are interested register soon in the course moodle and with the studienreferat.


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.


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 meet weekly on Monday, 17:00 - 18:30, in K-2.03. We will switch between in-person (with hybrid options) and zoom meetings as required. There will also be a dedicated slack channel for the course for further communication.

The first meeting on Monday April 17 at 17:00 will be virtual. Please see the Moodle page for the technical details.