PACE 2023 - Input and Output · PACE Challenge (original) (raw)

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:

• The vertices of an n-vertex graph are the numbers 1 to n.
• The line separator is \n.
• A line starting with c is a comment and has no semantics.
• The first non-comment line is the p-line:
  • It is formatted as p tww n m, where
  • n is the number of vertices;
  • m the number of edges to follow;
  • tww the problem descriptor.
• The p-line is unique and no other line starts with p.
• After the p-line there will be exactly m non-comment lines that encode the edges:
  • These are formatted as x y and define an edge between x and y, where x and y are numbers between 1 and n.

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 xxx and yyy is defined as follows:

• any edge (black or red) between xxx and yyy gets deleted;
• xxx retains all black edges to its neighbors that are adjacent to yyy;
• all edges from xxx to vertices that are not adjacent to yyy become red;
• xxx is connected with a red edge to all vertices that are connected to yyy but not to xxx;
• yyy gets deleted from the graph.

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

Contraction Sequences

A contraction sequence for a graph G=G1G=G_1G=G1 is a sequence of vertex pairs (x1,y1),(x2,y2),dots(x_1,y_1),(x_2,y_2),\dots(x_1,y_1),(x_2,y_2),dots such that:

• x_1x_1x1 and y1y_1y1 are (not necessarily connected) vertices in G1G_1G_1;
• contracting x_1x_1x1 and y1y_1y1 yields a new graph G2G_2G2, in which the vertices x2x_2x2 and y2y_2y_2 are present;
• the same argument holds inductively, that is, xix_ixi and yiy_iyi are vertices in GiG_iGi;
• after all contractions have been performed, a single vertex remains.

Validity of a Contraction Sequence

A contraction sequence is valid if:

• it contracts vertices at time iii that are present at time iii;
• it produces a single vertex graph.

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:

• Optional comment lines starting with c (as in the input);
• exactly n−1n-1n−1 contraction lines formatted as x y.

Here is an example:

Verifier

This Python script (version from 01.04.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 verifier.py <graph.gr> <result.tww>