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
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.
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.
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:
- 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.
- 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.
There will be three benchmark set:
- 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.
- The exact set containing 200 instances divided into 100 public instances for development and 100 private instances used for evaluation.
- The heuristic set containing 200 instances divided into 100 public instances for development and 100 private instances used for evaluation.
Details about the submission requirements can be found here.
- September 2022: Announcement of the Challenge
- October 2022: Definition of the input and output format.
- A tiny test set will be provided.
- A verifier will be provided.
- November 2022: Announcement of the ranking methods and additional information about the submission process.
December 2022January 2023: Public instances and details about the benchmark set get published.
- March 2023: Submission on optil.io opens with public leaderboard.
- May 2023: The public leaderboard gets frozen.
- June 2023: Submission Deadline.
- June 1st, 2023 (AoE): Submission deadline for solver.
- June 15th, 2023 (AoE): Submission deadline for solver description.
- July 2023: Announcement of the Results.
- IPEC 2023: Award ceremony.