Skip to main content
SpringerLink
Log in

A Fast and Effective Algorithm for the Feedback Arc Set Problem

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

A divide-and-conquer approach for the feedback arc set is presented. The divide step is performed by solving a minimum bisection problem. Two strategies are used to solve minimum bisection problem: A heuristic based on the stochastic evolution methodology, and a heuristic based on dynamic clustering. Empirical results are presented to compare our method with other approaches. An algorithm to construct test cases for the feedback arc set problem with known optimal number of feedback arcs, is also presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Berger, B. and P.W. Shor. (1990). “Approximation Algorithms for the Maximum Acyclic Subgraph Problem.” In Proc. First ACM-SIAM Symp. Discrete Algorithms. pp. 236–243.

  • Calazans, Ney, et al. (1992). “Advanced Ordering and Manipulation Techniques for Binary Decision Diagrams.” In European Design Automation Conference, Brussels, Belgium. pp. 452–457.

  • Cormen, T., C. Leiserson, and R. Rivest. (1990). Introduction to Algorithms. Cambridge, Mass: The MIT Press.

    Google Scholar 

  • De Souza, C., R. Keunings, L. Wolsey, and O. Zone. (1994). “A New Approach to Minimizing the Frontwidth in Finite Element Calculations.” Computer Methods in Applied Mechanics and Engineering 111(3/4), 323–334.

    Google Scholar 

  • Eades, P. and X. Lin. (To appear). “AHeuristic for the Feedback Arc Set Problem.”Australasian J. of Combinatorics.

  • Eades, P., X. Lin, and W.F. Smyth. (1993). “A Fast and Effective Heuristic for the Feedback Arc Set Problem.” Inf. Proc. Lett. 47, 319–323.

    Google Scholar 

  • Eades, P., W.F. Smyth, and X. Lin. (1989). “Heuristics for the Feedback Arc Set Problem.” Tech. Rept. 1, School of Computing Science, Curtin University of Technology, Perth, Western Australia.

    Google Scholar 

  • Ford, L. and D. Fulkerson. (1962). Flows in Networks. Princeton, NJ: Princeton University Press.

    Google Scholar 

  • Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY: W. H. Freeman and Company.

    Google Scholar 

  • Goldberg, A. and R. Tarjan. (1986). “A New Approach to the Maximum Flow Problem.” In Proc. Eight ACM Symp. on Theory of Computing. pp. 136–146.

  • Lempel, A. and I. Cederbaum. (1966). “Minimum Feedback Arc and Vertex Sets of a Directed Graph.” IEEET Trans. Circuit TheoryCT-13(4), 399–403.

    Google Scholar 

  • Lucchesi, C.L. (1976). “A Minimax Equality For Directed Graphs.” Doctoral Thesis, University of Waterloo, Ontario, Canada.

    Google Scholar 

  • Lucchesi, C.L. and D.H. Younger. (1978). “A Minimax Theorem For Directed Graphs.” J. London Math. Soc. 2(17), 369–374.

    Google Scholar 

  • Mitra, B., P. Ranjan Panda, and P. Pal Chaudhuri. (1993). “Estimating the Complexity of Synthesized Designs from FSM Specifications.” IEEE Design & Test of Computers 10(1), 30–35.

    Google Scholar 

  • Cherabuddi, Raghava V. and Magdy A. Bayoumi. (1994). “Automated System Partitioning for Synthesis of Multi-Chip Modules.” In Fourth Great Lakes Symposium on VLSI, Design Automation of High Performance VLSI Systems. pp. 21–25.

  • Ramachandran, V. (1988). “Finding Minimum Feedback Arc Set in Reducible Flow graphs.” J. Algorithms 9, 299–313.

    Google Scholar 

  • Saab, Y. (1990). “Combinatorial Optimization by Stochastic Evolution with Applications to the Physical Design of VLSI Circuits”. Doctoral Thesis, University of Illinois at Urbana-Champaign.

    Google Scholar 

  • Saab, Y. (1993). “Post-Analysis-Based Clustering Dramatically Improves the Fiduccia-Mattheyses Algorithm.” In European Design Automation Conference, Hamburg, Germany. pp. 22–27.

  • Saab, Y. (1995). “A Fast and Robust Network Bisection Algorithm.” IEEE Trans. Computers 44(7), 903–913.

    Google Scholar 

  • Saab, Y. and V. Rao. (1991). “Combinatorial Optimization by Stochastic Evolution.” IEEE Trans. Computer-Aided Design 10(4), 525–535.

    Google Scholar 

  • Seshu, S. and M.B. Reed. (1961). Linear Graphs and Electrical Networks. Reading, Mass: Addison Wesley.

    Google Scholar 

  • Slater, P. (1971). “Optimal Ranking of Tournaments.” Networks 1, 135–138.

    Google Scholar 

  • Unger, S.H. (1957). “A Study of Asynchronous Logical Feedback Networks.” Tech. Rept. 320, Research Lab. of Electronics, MIT, Cambridge, Mass.

    Google Scholar 

  • Younger, D.H. (1963). “Minimum Feedback Arc Sets for a Directed Graph.” IEEE Trans. Circuit Theory CT-10, 238–245.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Engineering and Computer Science Department, University of Missouri-Columbia, 321 Engineering Building West, Columbia, MO, 65211, USA

    Youssef Saab

Authors
  1. Youssef Saab
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Saab, Y. A Fast and Effective Algorithm for the Feedback Arc Set Problem. Journal of Heuristics 7, 235–250 (2001). https://doi.org/10.1023/A:1011315014322

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1011315014322

Search

Navigation