PACE 2020 Call for Participation

24 Oct 2019

We are happy to announce the fifth iteration of PACE, the Parameterized Algorithms and Computational Experiments Challenge. The goal of 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.

This year, the challenge is on treedepth (also see: a definition with figures):

  • Input: A connected undirected graph $G=(V,E)$
  • Output: A treedepth decomposition of $G$

Let us recall that a treedepth decomposition of a connected graph $G=(V,E)$ is a rooted tree $T=(V,E_T)$ such that every edge of $G$ connects a pair of nodes that have an ancestor-descendant relationship in $T$. The depth of $T$ is the maximum number of nodes in a root-vertex path in $T$. The treedepth of $G$ is a minimum depth of a treedepth decomposition of $G$.

Tracks

Two tracks are planned:

  1. Exact: Compute a treedepth decomposition of minimum depth. You have 30 minutes per instance. Contestants are ranked by number of instances solved and time required. Detailed ranking method will be published online.
  2. Heuristic: Compute some treedepth decomposition of decent depth. You have 30 minutes per instance. Contestants are ranked by quality of results and time required. Detailed ranking method will be published online.

Detailed instructions and public instances will be published later (see Timeline below)

Prizes

Thanks to the generous sponsoring of the NETWORKS project prize money and travel support is available for the winners of the competition.

Timeline

  • October 25th, 2019: Announcement of the challenge (Problem)
  • November 11th, 2019: Announcement of the tracks and additional information
  • December 16th, 2019: Public instances are available
  • March 13th, 2020: submiting via optil.io is running (for testing and unofficial, auxiliary leaderboard)
  • June 1st, 2020 (AOE) – Submission of final version (solver description two weeks after the code)
  • July, 2020: Announcement of the results
  • TBA / December 14-16, 2020 Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2020) in Hong Kong

Program Committee

  • Łukasz Kowalik (chair) (University of Warsaw)
  • Marcin Mucha (University of Warsaw)
  • Wojciech Nadara (University of Warsaw)
  • Marcin Pilipczuk (University of Warsaw)
  • Manuel Sorge (University of Warsaw)
  • Piotr Wygocki (University of Warsaw)

Steering Committee

  • Édouard Bonnet (LIP, ENS Lyon)
  • Holger Dell (IT University of Copenhagen)
  • Johannes Fichte (Technische Universität Dresden)
  • Markus Hecher (Technische Universität Wien)
  • Bart M. P. Jansen (chair) (Eindhoven University of Technology)
  • Petteri Kaski (Aalto University)
  • Christian Komusiewicz (Philipps-Universität Marburg)
  • Florian Sikora (LAMSADE, Université Paris Dauphine)

Related Posts