The First PACE Challenge

The goal of the Parameterized Algorithms and Computational Experiments Challenge (PACE) is to investigate the applicability of algorithmic ideas studied and developed in the subfields of multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms. In particular, it aims to

  • provide a bridge between the theory of design and analysis of algorithms and the algorithm engineering practice,
  • inspire new theoretical developments,
  • investigate the competitiveness of analytical and design frameworks developed in the communities,
  • produce universally accessible libraries of implementations and repositories of benchmark instances, and
  • encourage the dissemination of these findings in scientific papers.

The challenge will feature two tracks, Track A deals with the Tree Width Problem, and Track B deals with the Feedback Vertex Set Problem. The tracks have different aims: Track A has a broad scope including the call for algorithms that may solve the problem heuristically and for generators of hard instances. Track B aims for fixed-parameter algorithms that need to solve the Feedback Vertex Set problem exactly and has a fixed evaluation criterion. Therefore, Track B will have one or more winners that will be announced at IPEC 2016.

For each track, participation in the challenge essentially means submitting a program for the respective problem. During the algorithm development, the programs can be tested on a data set provided by the track chairs.

Due to the different aims of the two tracks, the technical requirements for submission differ somewhat. Moreover, since this is the first implementation challenge in parameterized algorithms, experimenting with different competition modes and submission formats may give valuable hints for future challenges.