Networks

PACE 2022: the results

PACE (the Parameterized Algorithms and Computational Experiments Challenge) is an implementation challenge for algorithms, aimed at students and junior researchers. Each year, the challenge is devoted to a different NP-hard problem. For such problems, it is widely believed that no efficient algorithm exists which finds an optimal solution for all inputs. The theory of parameterized algorithmics is aimed at such problems and investigates how to exploit structure that is present in real-life inputs to solve them more efficiently. The PACE challenge was conceived in 2015 to investigate the practical applicability of algorithmic ideas coming out of parameterized complexity.

 

 

paceThis year, the challenge was devoted to the Directed Feedback Vertex Set problem. This is a famous and elegant problem about networks. Given a network consisting of vertices and directed edges, the goal is to break all the cycles in the network by removing as few vertices as possible. This is a fundamental problem in the field of combinatorial optimization, but also has various practical applications such as in the area of deadlock resolution.

 

Over 26 teams participated, representing 12 teams spanning 3 different continents. The competition was split into an exact track (build an algorithm that is not allowed to make any mistakes) and a heuristic track (build an algorithm which even works for much larger inputs, which should output a solution which is close to but not necessarily optimal). The winning implementations combined a wide array of data-reduction rules to shrink the problem inputs, together with solvers for integer linear programming or constraint satisfaction problems. A key idea employed in multiple solvers was to use ‘lazy constraint generation’. A valid solution to the problem must break all the cycles. Since the number of distinct cycles in an input graph can be exponentially large in terms of the size of the graph, considering all cycles of the graph explicitly is very inefficient. A faster algorithm can be obtained by initially considering only a few strategically sampled cycles, only considering additional cycles when the solution under construction breaks all the sampled cycles but misses some cycle that has not yet been encoded into the algorithm. Andre Schidler and Rafael Kiesel (TU Wien) used this strategy to win the exact track, solving 185 out of the 200 benchmark inputs exactly. Sylwester Swat (Poznan University Of Technology) won the heuristic track, by using an approach based on agent flows to make an estimate of which vertices of the graph occur on many cycles.

 

The award ceremony for the competition was held at IPEC 2022, the International Symposium on Parameterized and Exact Computation. It took place in Potsdam, Germany. The next iteration of PACE has been announced: see www.pacechallenge.org for more information.