DreyFVS

DreyFVS is a solver for the Directed Feedback Vertex Set problem. It was submitted to the Heuristic Track of PACE Challenge 2022. This is an iterative solver applying two local search algorithms to improve a solution generated with a Sinkhorn-Knopp algorithm. More information can be found in the solver description

Requirements

• A 64-bit Linux operating system.
• A compiler, preferably GCC
• The cmake build system (>= 3.5.1).

Installation

To compile the code on a linux system you can use:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j

Using the program

The program uses standard input to read the input graph and print the solution in the standard output just before finishing. Some debug information is printed in the standard error. The input and output formats are described on the PACE 2022 - Heuristic Track Details.

The program can be used like that:

./build/DFVS < in.txt > out.txt

Then the solver runs for 10 minutes and stops when it receives a signal SIGTERM.