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

Instances

Tools

The following software tools are available:

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 Github or a similar platform that is publicly available. The following files are required.

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. We kindly ask all participants to send us an email by the submission deadline, including a link to their Github repository (or a similar platform). If your submission is eligible for the student ranking, please also include a brief note indicating this.

Docker Environment

A docker stack containing the evaluation environment is being prepared.

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

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

As in previous years, a preliminary leaderboard on optil will be available.

Zulip

Join us on Zulip for discussions and updates.

Program Committee