PACE 2026

Problem

This year features the Maximum-Agreement Forest (MAF) problem arising in phylogenetics (the study of evolutionary histories).

See also the Format Specification and the IPEC’25 Announcement Slides.

Timeline

Review Phase

Resources:

Please scrutize all the available algorithms and code. Feel free to reach out to the authors directly (preferred) or reach out to the PC.

Changes during Review Phase

The build scripts are tied to a specific reference commit hash, X, which corresponds to the most recent commit at the time the submission deadline passed. You may continue adding to your repository. As long as the reference commit X remains part of the Git history, we will simply ignore any later updates. If you would like us to update the reference commit, please contact both Alexander Leonhardt and Manuel Penschuck preferably via Zulip or via email. Please remember that the review phase is intended primarily for bugfixes.

Instances

Tools

The following software tools are available. There is no requirement to use them:

STRIDE

STRIDE is a tool that has two main objectives:

Results

No results yet.

Submission Guideline

We ask all participants to publish their codebase and solver description on Codeberg, Github, Gitlab (et cetera) or a ZIP/TAR archivew; the code needs to be publically accessible without registering with the platform. We will retrieve the sources shortly after the submission deadline. The following files are required.

Registration link: Registration form

Each team may submit up to three different solvers per track if they are substantially different (i.e. exploit different algorithmic ideas that substantially go beyond ‘parameter tweaking’). In this case, please submit one registration per solver and use different solver names.

The deadlines mentioned above apply. Note that changes on the codebase and the solver description after their respective deadlines are prohibited, except for small changes resulting from the reviewing phase in close contact with the organizers.

Solver Description

Each solver has to be accompanied by a solver description (PDF) that outlines the algorithmic and implementation details. For the exact and lower-bound tracks, we also ask teams to sketch why the solver is correct (no formal proof is required).

We recommend using the LIPIcs template, as in each track the three best-scoring teams will be invited to include a short-paper in the IPEC 2026 proceedings. After the official ranking has been published, we will reach out to these teams with submission instructions for these short papers.

The solver description is subject to a page limit of four pages (including the title page and bibliography). In case of a submission to multiple tracks, a shared description may be submitted; in this case, the page limit increases by three pages for each additional track.

To simplify the peer-review phase in July, please make sure to include an email address on the title page where other teams can report issues to you.

Tracks

The challenge features three distinct tracks:

  1. an “exact” track, solving MAF on an arbitrary number of trees – for this track, the instances come with precomputed values of some parameters (along with proofs, e.g. decompositions of certain width)
  2. a “heuristic” track, solving MAF on two trees – the instances will consist of two large trees and the allotted computation-time will be short
  3. a “lower-bound” track, also with two trees per instance – the aim is to reach an approximate solution quickly

Scoring

The scoring functions are applied for the final evalution of the submitted solvers. Please note that the scoring on optil deviates for technical reasons.

Exact track

Every correctly solved instance awards 1 point. Whenever a solver does not finish an instance in time (time + grace limit exceeded), this instance awards 0 points. If a solver produces an infeasible or suboptimal answer on any instance, it will be disqualified. Solvers achieving the same score will be ranked according to their total runtimes.

Lower-bound track

Depending on speed, every correctly solved instance awards between 0.5 and 1 points. Whenever a solver does not finish an instance in time (time + grace limit exceeded), this instance awards 0 points. If a solver produces an infeasible solution or a solution violating its size constraint (see below) on any instance, it will be disqualified.

Suppose that a suitable solution was produced in $t$ seconds in time (timeout of 10min + grace period of 10s). Then a score of $(2 - t/610)/2$ is awarded (i.e., 0.5 points for the solution and up to 0.5 points depending on speed).

In contrast to the exact track, suboptimal solutions are acceptable to a certain extend. Each instance contains an approximation line (#a) with two parameters $1 \le a < 1.5$ and $0 \le b$. Let $k^*$ be the (unknown) size of an MAF. Then, a solver needs to produce a solution of size at most $\lfloor a k^* \rfloor + b$; if a solver produces an infeasible solution or exceeds the instance-specific threshold, the solver will be disqualified.

Heuristic track

Depending on quality, every correctly solved instance awards between 0 and 1 points. Whenever a solver does not finish an instance in time (time +grace limit exceeded), this instance awards 0 points. If a solver produces an infeasible solution on any instance, it will be disqualified.

Fix an instance with $n$ leaves, and let $k^*$ be the best solution size known to the PC. Note that $k^* < n$ holds for every instance. Let $k$ be the solution produced by a solver and let $u = \min(n, 2\cdot k^*)$. The score for the instance is calculated according to the formula \(f(k) = \left(\max\left(0, \frac{u - k}{u - k^*}\right)\right)^2.\) This means that producing an optimal solution yields 1 point, producing a trivial solution or a solution outside factor 2 of the optimal solution yields 0 points, and improving an already good solution is more beneficial than improving a bad solution.

Overview

  Exact Track Lower-Bound Track Heuristic Track
Timeout 30min 10min 5min
Grace Time 10s 10s 10s
RAM 8 GB 8 GB 8 GB
Solution size Optimal $k^*$ $\le \lfloor a k^* \rfloor + b$ (see #a line) $\le n$
Instance score 1 per solved $(2 - t/610)/2$ with $t$: runtime (in sec) $\left(\max\left(0, [u - k]/[u - k^*]\right)\right)^2 $ with $k^*$: best known solution size, $k$: produced size, and $u = \min(n, 2k^*)$

Evaluation and correctness of exact and lower-bound solvers

This year we will again take special care to ensure the correctness of the exact and lower-bound solvers. We provide a large dataset of instances to test against, and highly recommend to STRIDE during development and before submission. Please make sure your solver treats corner cases, such as empty or edgeless intermediate trees correctly.

Shortly after submission, there will be a peer-review phase:

Preliminary leaderboard on optil

A preliminary leaderboard is available on optil. We strongly encourage all teams to submit their solvers.

Zulip

Join us on Zulip for discussions and updates.

Program Committee