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.

arXiv comment14 pages

References in corpus (11)

• The Bethe lattice spin glass revisited
• Learning by message-passing in networks of discrete synapses
• Spin glass approach to the feedback vertex set problem
• Random numbers for large scale distributed Monte Carlo simulations
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Inherent directionality explains the lack of feedback loops in empirical networks
• Belief propagation for graph partitioning
• Feedback arcs and node hierarchy in directed networks

Cited by in corpus (4)

• The characteristics of cycle-nodes-ratio and its application to network classification
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
• Hierarchical cycle-tree packing model for $K$-core attack problem