Title: Optimal segmentation of directed graph and the minimum number of feedback arcs,
Abstract: The minimum feedback arc set problem asks to delete a minimum number of arcs
(directed edges) from a digraph (directed graph) to make it free of any
directed cycles. In this work we approach this fundamental cycle-constrained
optimization problem by considering a generalized task of dividing the digraph
into D layers of equal size. We solve the D-segmentation problem by the
replica-symmetric mean field theory and belief-propagation heuristic
algorithms. The minimum feedback arc density of a given random digraph ensemble
is then obtained by extrapolating the theoretical results to the limit of large
D. A divide-and-conquer algorithm (nested-BPR) is devised to solve the minimum
feedback arc set problem with very good performance and high efficiency.