Minimal and stable feedback arc sets and graph centrality measures
Claudia Cavallaro, Vincenzo Cutello, Mario Francesco Pavone · Computers & Operations Research · 2025
In this paper we tackle one of the most famous problems in graph theory and, in general, in the area of discrete optimization, namely the Minimum Feedback Arc Set Problem for a directed graph. In particular, we study the problem using the methodology of the linear arrangements of the vertices to find feedback arc sets, and an optimization heuristic to reduce their size. We test the efficacy of the heuristic against several linear arrangements of the vertices obtained by using some well known centrality metrics. We experimentally show that, independently from the linear arrangement used, our heuristic methodology obtains feedback arc sets with an average approximation ratio not greater than $1.4$. • The minimum feedback arc set problem and linear arrangements of the vertices. • Centrality and degree metrics to produce linear arrangements of the vertices. • Efficacy of the heuristic in obtaining feedback arc sets of minimal size. • An optimization heuristic to reduce of about 50% the size of feedback arc set found.