Dynamic thresholding search for the feedback vertex set problem

Given a directed graph G = (V, E), a feedback vertex set is a vertex subset C whose removal makes the graph G acyclic. The feedback vertex set problem is to find the subset C* whose cardinality is the minimum. As a general model, this problem has a variety of applications. However, the problem is known to be NP-hard, and thus computationally challenging. To solve this difficult problem, this article develops an iterated dynamic thresholding search algorithm, which features a combination of local optimization, dynamic thresholding search, and perturbation. Computational experiments on 101 benchmark graphs from various sources demonstrate the advantage of the algorithm compared with the state-of-the-art algorithms, by reporting record-breaking best solutions for 24 graphs, equally best results for 75 graphs, and worse best results for only two graphs. We also study how the key components of the algorithm affect its performance of the algorithm.

Automated summary

In a directed graph G = (V, E), a feedback vertex set is a subset C that, when removed, makes the graph G acyclic. The feedback vertex set problem aims to find the minimum cardinality subset C*. This problem has various applications but is known to be NP-hard, posing computational challenges. To tackle this problem, the article proposes an iterated dynamic thresholding search algorithm that combines local optimization, dynamic thresholding search, and perturbation. Computational experiments on 101 benchmark graphs show that the algorithm outperforms state-of-the-art algorithms, achieving record-breaking best solutions for 24 graphs, equally best results for 75 graphs, and worse best results for only two graphs. The article also examines the impact of key components on the algorithm's performance.