Minimal and stable feedback arc sets and graph centrality measures
研究了有向图的最小反馈弧集问题，利用顶点线性排列和中心性度量设计启发式算法，能将反馈弧集大小平均减少约50%，近似比不超过1.4。
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.