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.

Results of the Challenge

We are happy to announce the results of PACE 2023. Congratulations to the winners and all the participants

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 can be found here.

Tracks

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

Details about the scoring methods can be found here.

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 30 minutes and a memory limit of 8 GB.

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 Heuristic Track

In this track the solver shall compute a good solution quickly. The solver will be run on each instance for 5 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. The memory limit for this track is 8 GB as well.

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

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. On optil.io this set as a time limit of 60 seconds and memory limit of 100 Kb.
  2. The exact set containing 200 instances divided into 100 public instances for development and 100 private instances used for evaluation.
  3. The heuristic set containing 200 instances divided into 100 public instances for development and 100 private instances used for evaluation.

Submission

Details about the submission requirements can be found here.

Timeline

Program Committee