Optimal segmentation of directed graph and the minimum number of feedback arcs

DOI10.1007/S10955-017-1860-5MaRDI QIDQ1683994zbMATH OpenOpenAlexFDO

Authors Yi-Zhi Xu, Haijun Zhou

Publication date 4 December 2017

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.05946

zbMATH Keywords

algorithmsegmentationdirected cyclefeedback arc setmean field theorybelief propagationreplica-symmetric

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

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.

Recommendations

• An exact method for the minimum feedback arc set problem
• A spin glass approach to the directed feedback vertex set problem
• A fast and effective algorithm for the feedback arc set problem
• Combinatorial algorithms for feedback problems in directed graphs
• A fast and effective heuristic for the feedback arc set problem

Cites work

• A spin glass approach to the directed feedback vertex set problem
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph.
• Belief propagation for graph partitioning
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Decycling numbers of random regular graphs
• Information, Physics, and Computation
• Lie symmetry and Hojman conserved quantity of Nielsen equation in a dynamical system of the relative motion
• Loop Calculus For Nonbinary Alphabets Using Concepts From Information Geometry
• Maximum acyclic and fragmented sets in regular graphs
• Partition function loop series for a general graphical model: free-energy corrections and message-passing equations
• Reducibility among combinatorial problems
• Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results
• Spin Glass approach to the feedback vertex set problem

Cited in

(4)

• Hierarchical cycle-tree packing model for optimal \(K\)-core attack
• Finding a minimum feedback arc set in reducible flow graphs
• The characteristics of cycle-nodes-ratio and its application to network classification
• A fast and effective algorithm for the feedback arc set problem

Describes a project that uses

Uses Software

• trng

This page was built for publication: Optimal segmentation of directed graph and the minimum number of feedback arcs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1683994)