We are happy to announce the 11th iteration of PACE, the Parameterized
Algorithms and Computational Experiments Challenge. The goals of PACE,
as well as official reports for past challenges, can be found on our
website: https://pacechallenge.org/.
** Challenge Problem
------------------------------------------------------------
This year, the challenge is about rooted maximum-agreement forests,
arising in phylogenetics, i.e. the study of evolutionary histories.
Consider a set of rooted trees T1, T2, ..., Tt with the same set X of
leaves (leaf-labels).
A forest of rooted trees is called a *rooted agreement forest* if
(i) the leaves of F are labelled with X, and
(ii) each Ti can be translated into F by first removing directed edges
and then contracting vertices with out-degree at most one.
Input: A list of phylogenetic trees on the same leaf-set X.
Output: A smallest agreement forest of all input trees.
** Tracks
------------------------------------------------------------
Three tracks are planned:
Exact: Given t≥2 rooted trees on the same leaf-set, compute a smallest
agreement forest in a given timeframe. Contestants are ranked by number
of instances solved and time required.
NOTE: In this track, the instances will be augmented with information
about various parameters (such as their value and a proof thereof). To
this end, we would like to encourage participants to suggest parameters
that can be computed/estimated for the instances.
Heuristic: Given t=2 rooted trees on the same leaf-se, compute an
agreement forest with as few trees as possible in a given timeframe.
Contestants are ranked by the sizes of the forests and the times
required to optain them.
Lower Bound: Given t=2 rooted trees on the same leaf-set, compute an
agreement forest whose size must fall within a certain radius around the
smallest (known) agreement forest. Valid solutions are ranked by the
time it took to compute them.
Detailed instructions, details about the ranking methods and public
instances will be published online at a later point.
** Timeline
------------------------------------------------------------
October'25: Announcement of the challenge (Problem) and tracks
November'25: Release of tiny instances and test-environment
TBA / January'26: Release of public instances
TBA / April'26: Submissions via Optil.io open
TBA / July'26: Submission of final version, announcement of results
TBA / September'26: Award ceremony at the International Symposium on
Parameterized and Exact Computation (IPEC 2026).
** Zulip
------------------------------------------------------------
Join us on Zulip for discussions and updates:
https://pacechallenge.zulipchat.com/join/l3eavdfbytkcjiypecpzetuw/
** Program Committee
------------------------------------------------------------
Alexander Leonhardt (Goethe University, Frankfurt)
Manuel Penschuck (University of Southern Denmark, Odense)
Mathias Weller (CNRS, Université Gustave Eiffel, Paris)
** Steering Committee
------------------------------------------------------------
Max Bannach (European Space Agency)
Sebastian Berndt (Universität zu Lübeck)
Holger Dell (Goethe University Frankfurt, IT University of Copenhagen)
Bart M. P. Jansen (chair) (Eindhoven University of Technology)
Philipp Kindermann (Universität Trier)
André Nichterlein (Technical University of Berlin)
Christian Schulz (Universität Heidelberg)
Soeren Terziadis (TU Eindhoven)
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
