PACE 2016 Feedback Vertex Set (PACE 2016 Track B, Feedback Vertex Set)

This is the dataset used in the PACE 2016 challenge, Track B, which was computing minimal Feedback Vertex Set. This competition focused on exact solutions, i.e. provably minimal feedback vertex sets (and no heuristic solutions). This should not be confused with the PACE 2022 challenge, which focused on directed feedback vertex set, and has its own entries on PapersWithCode (exact and heuristic).

The dataset can be downloaded here, and includes 100 instances that were released for practice (the public/ folder) and 100 instances that were kept private (hidden/) until the competition evaluation. All 200 were used in the final evaluation. Each instance is an undirected graph, one edge per line, in the format a b indicating an edge between vertices a and b. Vertices are 1-indexed.

Final results of the competition were reported in the PACE report, and additional analysis of some top solutions was done independently by Kiljan and Pilipczuk.