PACE 2022 Exact (PACE 2022 Directed Feedback Vertex Set, Exact Track)

This is the set of graphs used in the PACE 2022 challenge for computing the Directed Feedback Vertex Set, from the Exact track. It consists of 200 labelled directed graphs. The graphs range in size up to from N=512 up to N=131072 vertices, and up to 1315170 edges. The graphs are mostly not symmetric (an edge form u->v does not imply an edge from v->u), although some are symmetric. The graph labels are integers ranging from 1 to N.

There is the related PACE 2022 Heuristic dataset, which allowed for approximate solutions (feedback vertex sets that were not necessarily of minimum size). Those graphs are generally larger and denser, as approximate solutions were still accepted.

The data format begins with one line N E 0, where N is the number of vertices, E is the number of edges, and 0 is the literal integer zero. The N subsequent lines are each a space-separated list of integers, such as 2 5 11 19. If that appeared on line number 1 (the first after N E 0), it would indicate that there are edges from vertex 1 to each of the vertices 2, 5, 11, and 19. Some lines are blank, and these indicates vertices with outdegree zero. An example graph would be

4 4 0
2 3
3

1

The dataset can be downloaded here. The 100 instances that were available for public testing are precisely the odd-numbered ones in that link; the public instances can be downloaded on their own here.