Second place in PACE Challenge 2020

25.6.2020
The SMS solver implemented by Tuukka Korhonen reached second place in the exact treedepth track of 5th Parameterized Algorithms and Computational Experiments Challenge.

PACE is an algorithm implementation competition, with the purpose of bridging the divide between theory and practice in parameterized algorithms. The topic of PACE 2020 was computation of the graph parameter treedepth.

The SMS solver by Tuukka Korhonen of the Constraint Reasoning and Optimization group took the second place in the exact treedepth track of PACE 2020, solving 77 instances out of 100, only one less than the winning solver. SMS is based on branching on small minimal separators of the graph. The solver is available in open source here. For more details on the approach, see the accompanying description.

The full results of PACE 2020 are available here.