PACE 2023 - Input and Output

The task of this year’s challenge is to compute an optimal contraction sequence of a given undirected graph.

The Input Format

The graph is presented as input in essentially the same graph (.gr) format used in previous iterations of the challenge:

Note that this format allows to encode isolated vertices, multi-edges, and self-loops. Here is an example:

c This file describes a graph with 6 vertices and 4 edges.
p tww 6 4
1 2
2 3
c This is a comment and will be ignored.
4 5
4 6

Contracting two Vertices

The contraction of two vertices $x$ and $y$ is defined as follows:

Note that in this definition, the contraction operation is not symmetric, that is, contracting $(x,y)$ results in a different (but isomorphic) graph than contracting $(y,x)$.

Contraction Sequences

A contraction sequence for a graph $G=G_1$ is a sequence of vertex pairs $(x_1,y_1),(x_2,y_2),\dots$ such that:

Validity of a Contraction Sequence

A contraction sequence is valid if:

The width of a contraction sequence is the maximum red degree that appears during the contraction process.

Output Format

The output of this year’s challenge is the twinwidth format tww that contains:

Here is an example:

1 2
1 3
4 5
4 6
1 6


This Python script (version from 15.02.2023) can be used to check whether a given contraction sequence is valid for a given graph. The output will either be the sequence width or an error message.

 python <> <result.tww>