Solving the directed feedback vertex set problem in theory and practice

A directed feedback vertex set (dfvs) is a subset of vertices of a graph, that, when removed, makes the graph acyclic. The Directed Feedback Vertex Set problem (DFVS) is to find such a subset. It is NP-complete, hence, we do not know how to solve it efficiently.

In this work we explore practical approaches to find a minimum dfvs on real word instances. This was also the goal of the Parameterized Algorithms and Computational Experiments (PACE) challenge 2022. Our submission obtained the second place in the exact track and was the best student team.

Our first step of finding a minimum dfvs is to apply a set of data reduction rules. These are applied in polynomial time and reduce the size of the instance. We give a detailed overview of existing and new data reduction rules.

A kernel can be seen as a collection of reduction rules with theoretical guarantees. It is a polynomial time algorithm that takes a problem instance and returns a smaller equivalent instance with a bound on its size. We show that a very simple reduction rule removes the input restriction for the kernel of Bergougnoux et al. (2021). After its application, we obtain an instance with at most O(f^4) vertices, with f being the size of a minimum feedback vertex set on its cycle preserving undirected graph.

We implemented several techniques to solve a reduced instance. We achieved best results when performing an iterative reduction to Hitting Set, which we then either reduce to Integer Linear Program, Max SAT or Vertex Cover. Solvers for these three problems already exist, which can solve large instances in practice.

Depending on the instance, we select the best suitable solving approach. For the first time, we explain the solver that we submitted in detail and present an improved version. We compare our results with approaches of other challenge participants, in particular DAGer, the winner of the exact track. Our improved solver is now able to solve the same number of instances within the time limit of the PACE challenge.