PACE 2023

This year’s challenge is about twinwidth, a graph parameter that (intuitively) measures the distance of a graph to a co-graph. The parameter was introduced in 2020 and has lead to a multitude of theoretical results since then.

Challenge Description

The goal of this year’s challenge is to compute a contraction sequence for a given graph of small width. More precisely:

Input: An undirected graph $G=(V,E)$.
Output: A contraction sequence that contracts $G$ to a single vertex.
Measure: The width of the contraction sequence.

Details about the input and output format will be made available in October.

Tracks

As in previous incarnations of the challenge, we will have two tracks: One focusing on Exact algorithms and one for Heuristic solutions.

The Exact Track

The task is to compute an optimal solution for each given graph, that is, a contraction sequence of minimum width. For each instance, the solver has to output a solution within a time limit of $x$ minutes.

Submissions should be based on provably optimal algorithms, however, this is not a formal requirement. Submissions that output an incorrect solution or a solution that is known to be non-optimal will be disqualified. Besides dedicated algorithms, we also encourage submissions based on other paradigms such as SAT, MaxSAT, or ILPs.

The scoring-scheme and the precise value of $x$ will be announced in November.

The Heuristic Track

In this track the solver shall compute a good solution quickly. The solver will be run on each instance for $y$ minutes and receives the Unix signal SIGTERM afterwards. When receiving this signal, the process has to output a correct contraction sequence immediately to the standard output and terminate. If the program does not halt in a reasonable time after reserving the signal, it will be stopped via SIGKILL. In this case the instance is counted as time limited exceeded. Information on how to handle Unix signals in various programming languages can be found on the optil.io webpage.

For this track solutions do not have to be optimal. However, solvers that produce incorrect solution will be disqualified.

The scoring-scheme and the precise value of $y$ will be announced in November.

Theory Awareness

Very little is known about computational aspects of twinwidth. There is a reasonable effective SAT-encoding and a proof that it is already hard to test whether a graph has twinwidth at most four. Since one of the goals of the challenge is to bridge the gap between theory and practice, we encourage submissions that are baked with new theoretical insights. This year’s incarnation of the PACE supports this idea in two ways:

  1. The instance sets will contain some instances from predefined graph classes (such as planar graphs, twinwidth 2 graphs, etc.). Solvers can thus specialize, to a certain degree, to specific inputs.
  2. We will give an extra Theory Award to the submission with the most interesting theoretical guarantee that has to be documented in the solver description.

Benchmark Sets

There will be three benchmark set:

  1. A tiny set for debugging that contains graphs together with their twinwidth.
    • This set will be made available in October.
  2. The exact set containing 200 instances divided into 100 public instances for development and 100 private instances used for evaluation.
    • The public instances will be made available in December; the private instances after the challenge.
  3. The heuristic set containing 200 instances divided into 100 public instances for development and 100 private instances used for evaluation.
    • The public instances will be made available in December; the private instances after the challenge.

Submission

Details about the submission requirements will be provided in November.

Timeline

Program Committee