Test Instances for the Treewidth Problem

Test instances for the Treewidth Problem.

All the instances are provided by the 2017 PACE Challenge (Dell et al., 2018) on the Heuristic Track.

The graph format is a simple text format. Lines are separated by the character ‘\n’. Each line that starts with the character c is considered to be a comment line. The first non-comment line must be a line starting with p followed by the problem descriptor tw and the number of vertices n and edges m (separated by a single space each time). No other line may start with p. Every other line indicates an edge, and must consist of two decimal integers from 1 to n separated by a space; moreover, graphs are considered undirected (though they may contain isolated vertices, multiple edges, and loops). For example, a path with four edges can be defined as follows:

c This file describes a path with five vertices and four edges.
p tw 5 4
1 2
2 3
c we are half-way done with the instance definition.
3 4
4 5

Vertex names can be any combination of letters, digits, and _. Lines starting with ‘#’ are comments. Note that this graph format cannot describe zero-degree vertices (which are irrelevant for Chordal Completion anyway).

Reference:
-----------
Dell, H., Komusiewicz, C., Talmon, N., Weller, M., 2018. The pace 2017 parameterized algorithms and computational experiments challenge: The second iteration, in: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.