For PACE 2022, we offer the following two tracks:
You can participate in any subset of the two tracks.
Exact Track
Your submission should find an optimal (minimum) feedback vertex set (see also the problem description) within 30 minutes. We expect your submission to be an exact algorithm, although we do not ask you to provide a proof of it. If we find through code checks or experiments that your algorithm is not an exact algorithm, then it will be excluded from the track. If for some instance your program returns a solution that is not optimal within the time limit, either because it is not minimum or not a feedback vertex set, then your submission will be disqualified. See also the input format and output format.
Ranking method: You will be ranked by the number of solved instances. In case of a tie, the winner is determined by the time required to solve all instances.
You can download a tar.gz file containing all public instances for the exact track here.
UPDATE: You can download a tar.gz file containing all instances (public+private) for the exact track here.
Heuristic Track
Your submission should find a feedback vertex set (see also the problem description) within 10 minutes. See also the input format and output format.
Termination:
Your program will receive the Unix signal SIGTERM on timeout.
When your process receives this signal, it must immediately print the current best solution to the standard output and then halt.
You can find examples how to handle SIGTERM in several popular programming languages.
If the process blocks for too long, say 30 seconds after the initial SIGTERM signal, we will forcefully stop it with SIGKILL.
If we forcefully stopped the program, then the instance counts as time limit exceeded and solution size will be considered as |V|.
Note that the optil.io system may not work 100% correctly all the time, i.e. the default of your program should be that your program returns a solution after 10 minutes.
Ranking method:
You will be ranked by the geometric mean over all instances of 100 × (best solution size) / (solution size).
Here, (solution size) is the size of the solution returned by your submission and (best solution size) is the size of the smallest solution known to the PC (which may not be optimal).
If the output of your program turns out to be not a feedback vertex set, your program will be disqualified. Note that the optil.io platform ranking differs here slightly due to technical reasons: on optil.io if the output of your program turns out to be not a feedback vertex set, it will use |V|.
If your program does not return an output on SIGKILL for some instance, (solution size) for the instance will be considered as |V|.
You can download a tar.gz file containing all public the instances for the heuristic track here.
UPDATE: You can download a tar.gz file containing all instances (public + private) for the heuristic track here.
Input Format
The input graph is given via the standard input, which follows the Metis file format described below.
Lines are separated by the character \n. Each line that starts with the character % is considered to be a comment line.
The first non-comment line contains the number of vertices n and edges m and an identifier t (separated by a single space each time). The identifier t indicates whether the graph
contains node or edge weights. Since we only consider unweighted graphs, t will always equal 0.
The next n non-comment lines contain the adjacency lists of the nodes. Let $L = {l_1, \ldots, l_n}$ denote these lines.
Then, each line $l_u$ is of the form v1 v2 ... vl (separated by a single space each time) representing the adjacency list of node u. That means u is connected to v1 by an edge (u,v1), and to v2 by an edge (u,v2) and so forth. Note that the nodes are numbered 1 to n.
Moreover, graphs are considered to be directed and simple, i.e. parallel edges and self-loops are forbidden. For example, a graph with four vertices and five directed edges can be defined as follows:
% This file describes a directed graph with four vertices and five directed edges.
4 5 0
2 3
3
% we are half-way done with the instance definition.
4
1
Output Format
Every line must be in the form u followed by the new line character \n, where u represents a node contained in your feedback vertex set. Here is an example:
1
2
Use this to verify whether the output is a feedback vertex set.
To compile this verifier for feedback vertex set execute make all in the command line.
Afterwards, there is an executable verifier.
The verifier takes two arguments: paths to an input graph file and a solution file containing the solution (see output format).
Note that it does not check for optimality.
The instances for both tracks will be available to download in January 2022.
Example Instances and Solutions
Download example instances with solutions here.