Extended PACE 2023 Input Format

We extend the PACE 2023 input format (PACE 2023 - Input and Output) to accept trigraphs -- graphs with edges pre-colored in either black or red. Also, an input file may contain known bounds for twin-width.

• The line separator is \n.
• A line starting with c is a comment and has no semantics.

p-line

p twwe {n} {m} [{ub} [{lb}]]

• The first non-comment line is the p-line:
  • twwe the problem descriptor (short for TWin-Width Extended);
  • {n} the number of vertices ($n$) in $G$;
  • {m} the number of edges ($m$) in $G$;
  • {ub} (optional) a known upper-bound of the twin-width of the input graph.
  • {lb} (optional) a known lower-bound of the twin-width of the input graph.
• The p-line is unique and no other line starts with p.

Vertex list

v {v}

• After the p-line there will be exactly $n$ non-comment lines that encode vertex labels.
• The vertices in $G$ are labeled by non-negative integers $[0, 2^{32})$, not necessarily consecutive.
  • {v} a vertex label

Edge list

e {u} {v} [{color}]

• After the vertex list there will be exactly $m$ non-comment lines that encode the edges:
• Defines an edge $uv$ with color color.
  • {u} and {v} vertex labels
  • {color} (optional) either 0 or 1:
    • 0: black edge [default]
    • 1: red edge

Example

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

In this example, twin-width is upper-bounded by $3$. Edges $\{1,2\}$ and $\{2,3\}$ are black edges, and $\{4,5\}$ and $\{4,6\}$ are red edges.