Targeting the minimum vertex set problem with an enhanced genetic algorithm improved with local search strategies

The minimum feedback vertex set in a directed graph is a NP-hard problem i.e., it is very unlikely that a polynomial algorithm can be found to solve any instances of it. Solutions of the minimum feedback vertex set can find several real world applications. For this reason, it is useful to investigate heuristics that might give near-optimal solutions. Here we present an enhanced genetic algorithm with an ad hoc local search improvement strategy that finds good solutions for any given instance. To prove the effectiveness of the algorithm, we provide an implementation tested against a large variety of test cases. The results we obtain are compared to the results obtained by greedy and randomized algorithms for finding approximate solutions to the problem.