{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:38:36Z","timestamp":1765960716846,"version":"3.48.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T00:00:00Z","timestamp":1752278400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T00:00:00Z","timestamp":1752278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["CCF-2109988"],"award-info":[{"award-number":["CCF-2109988"]}]},{"name":"National Science Foundation","award":["CCF-2109988"],"award-info":[{"award-number":["CCF-2109988"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Understanding information flow in the brain can be facilitated by arranging neurons in the fly connectome to form a maximally \u201cfeedforward\u201d structure. This task is naturally formulated as the Minimum Feedback Arc Set (MFAS)\u2014a well-known NP-hard problem, especially for large-scale graphs. To address this, we propose the Rocket-Crane algorithm, an efficient two-phase method for solving MFAS. In the first phase, we develop a continuous-space optimization method that rapidly generates excellent solutions. In the second phase, we refine these solutions through advanced exploration techniques that integrate randomized and heuristic strategies to effectively escape local minima. Extensive experiments demonstrate that Rocket-Crane outperforms state-of-the-art methods in terms of solution quality, scalability, and computational efficiency. On the primary benchmark\u2014the fly connectom\u2014our method achieved a feedforward arc set with a total forward weight of 35,459,266 (about 85\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\%$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mo>%<\/mml:mo>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    ), the highest among all competing methods. The algorithm is open-source and available on GitHub.\n                  <\/jats:p>","DOI":"10.1007\/s13278-025-01491-2","type":"journal-article","created":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T08:32:31Z","timestamp":1752309151000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Rocket-crane algorithm for the Feedback Arc Set problem"],"prefix":"10.1007","volume":"15","author":[{"given":"David A.","family":"Bader","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Ellis-Joyce","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gert-Jan","family":"Both","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivas C.","family":"Turaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harinarayan","family":"Asoori Sriram","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srijith","family":"Chinthalapudi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhihui","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,12]]},"reference":[{"issue":"5","key":"1491_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1411509.1411513","volume":"55","author":"N Ailon","year":"2008","unstructured":"Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: ranking and clustering. JACM 55(5):1\u201327","journal-title":"JACM"},{"key":"1491_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3446429","volume":"26","author":"A Baharev","year":"2021","unstructured":"Baharev A, Schichl H, Neumaier A, Achterberg T (2021) An exact method for the minimum feedback arc set problem. J Exp Algorithmics (JEA) 26:1\u201328","journal-title":"J Exp Algorithmics (JEA)"},{"key":"1491_CR3","unstructured":"Baweja A, Jia J, Woodruff DP (2021) An efficient semi-streaming PTAS for tournament Feedback ArcSet with Few Passes. arXiv preprint arXiv:2107.07141"},{"key":"1491_CR4","unstructured":"Berger B, Shor PW (1990) Approximation algorithms for the maximum acyclic subgraph problem. In: Proceedings of the first annual ACM-SIAM symposium on discrete algorithms, pp 236\u2013243"},{"issue":"6","key":"1491_CR5","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.1016\/j.jcss.2010.10.001","volume":"77","author":"S Bessy","year":"2011","unstructured":"Bessy S, Fomin FV, Gaspers S, Paul C, Perez A, Saurabh S, Thomass\u00e9 S (2011) Kernels for feedback arc set in tournaments. J Comput Syst Sci 77(6):1071\u20131078","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"1491_CR6","doi-asserted-by":"publisher","first-page":"1011904","DOI":"10.1371\/journal.pcbi.1011904","volume":"20","author":"A Borst","year":"2024","unstructured":"Borst A (2024) Connectivity matrix seriation via relaxation. PLoS Comput Biol 20(2):1011904","journal-title":"PLoS Comput Biol"},{"key":"1491_CR7","unstructured":"Brandenburg FJ, Hanauer K (2011) Sorting heuristics for the feedback arc set problem. University of Passau, Department of Informatics and Mathematics"},{"key":"1491_CR8","doi-asserted-by":"crossref","unstructured":"Buluc A, Kolda TG, Wild SM, Anitescu M, Degennaro A, Jakeman J, Kamath C, Kannan R, Lopes ME, Martinsson P-G et al (2021) Randomized algorithms for scientific computing (RASC). arXiv preprint arXiv:2104.11079","DOI":"10.2172\/1807223"},{"key":"1491_CR9","doi-asserted-by":"crossref","unstructured":"Chen J, Liu Y, Lu S, O\u2019sullivan B, Razgon I (2008) A fixed-parameter algorithm for the directed feedback vertex set problem. In: Proceedings of the fortieth annual ACM symposium on theory of computing, pp 177\u2013186","DOI":"10.1145\/1374376.1374404"},{"key":"1491_CR10","unstructured":"Diamond H, Kon M, Raphael L (2024) Asymptotic lower bounds for the feedback arc set problem in random graphs. arXiv preprint arXiv:2409.16443"},{"key":"1491_CR11","doi-asserted-by":"crossref","unstructured":"Dinur I, Safra S (2002) The importance of being biased. In: Proceedings of the thiry-fourth annual ACM symposium on theory of computing, pp 33\u201342","DOI":"10.1145\/509907.509915"},{"issue":"1","key":"1491_CR12","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1109\/TCT.1968.1082764","volume":"15","author":"L Divieti","year":"1968","unstructured":"Divieti L, Grasselli A (1968) On the determination of minimum feedback arc and vertex sets. IEEE Trans Circuit Theory 15(1):86\u201389","journal-title":"IEEE Trans Circuit Theory"},{"issue":"8032","key":"1491_CR13","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1038\/s41586-024-07558-y","volume":"634","author":"S Dorkenwald","year":"2024","unstructured":"Dorkenwald S, Matsliah A, Sterling AR, Schlegel P, Yu S-C, McKellar CE, Lin A, Costa M, Eichler K, Yin Y et al (2024) Neuronal wiring diagram of an adult brain. Nature 634(8032):124\u2013138","journal-title":"Nature"},{"key":"1491_CR14","first-page":"15","volume":"12","author":"P Eades","year":"1995","unstructured":"Eades P, Lin X (1995) A heuristic for the feedback arc set problem. Australas J Comb 12:15\u201326","journal-title":"Australas J Comb"},{"issue":"6","key":"1491_CR15","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0020-0190(93)90079-O","volume":"47","author":"P Eades","year":"1993","unstructured":"Eades P, Lin X, Smyth WF (1993) A fast and effective heuristic for the feedback arc set problem. Inf Process Lett 47(6):319\u2013323","journal-title":"Inf Process Lett"},{"key":"1491_CR16","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G Even","year":"1998","unstructured":"Even G, Naor J, Schieber B, Sudan M (1998) Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20:151\u2013174","journal-title":"Algorithmica"},{"issue":"2","key":"1491_CR17","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1002\/rsa.21179","volume":"64","author":"J Fox","year":"2024","unstructured":"Fox J, Himwich Z, Mani N (2024) Extremal results on feedback arc sets in digraphs. Random Struct Algorithms 64(2):287\u2013308","journal-title":"Random Struct Algorithms"},{"key":"1491_CR18","doi-asserted-by":"publisher","first-page":"1048","DOI":"10.1007\/s00224-017-9777-6","volume":"62","author":"M Hecht","year":"2018","unstructured":"Hecht M (2018) Exact localisations of feedback sets. Theory Comput Syst 62:1048\u20131084","journal-title":"Theory Comput Syst"},{"key":"1491_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3447652","volume":"26","author":"M Hecht","year":"2021","unstructured":"Hecht M, Gonciarz K, Horv\u00e1t S (2021) Tight localizations of feedback sets. J Exp Algorithmics (JEA) 26:1\u201319","journal-title":"J Exp Algorithmics (JEA)"},{"issue":"11","key":"1491_CR20","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/368996.369025","volume":"5","author":"AB Kahn","year":"1962","unstructured":"Kahn AB (1962) Topological sorting of large networks. Commun ACM 5(11):558\u2013562","journal-title":"Commun ACM"},{"key":"1491_CR21","unstructured":"Kann V (1992) On the approximability of NP-complete optimization problems. PhD thesis, Royal Institute of Technology Stockholm"},{"key":"1491_CR22","doi-asserted-by":"crossref","unstructured":"Karp RM (2009) Reducibility among combinatorial problems. In: 50 Years of integer programming 1958\u20132008: from the Early Years to the State-of-the-Art. Springer, Berlin, pp 219\u2013241","DOI":"10.1007\/978-3-540-68279-0_8"},{"key":"1491_CR23","doi-asserted-by":"crossref","unstructured":"Kenyon-Mathieu C, Schudy W (2007) How to rank with few errors. In: Proceedings of the thirty-ninth annual ACM symposium on theory of computing, pp 95\u2013103","DOI":"10.1145\/1250790.1250806"},{"key":"1491_CR24","unstructured":"Kokash N (2005) An introduction to heuristic algorithms. Department of Informatics and Telecommunications 1, 1\u20137"},{"key":"1491_CR25","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.eswa.2018.12.021","volume":"122","author":"R Kudeli\u0107","year":"2019","unstructured":"Kudeli\u0107 R, Ivkovi\u0107 N (2019) Ant inspired Monte Carlo algorithm for minimum feedback arc set. Expert Syst Appl 122:108\u2013117","journal-title":"Expert Syst Appl"},{"issue":"2","key":"1491_CR26","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1109\/TCT.1964.1082291","volume":"11","author":"E Lawler","year":"1964","unstructured":"Lawler E (1964) A comment on minimum feedback arc sets. IEEE Trans Circuit Theory 11(2):296\u2013297","journal-title":"IEEE Trans Circuit Theory"},{"issue":"4","key":"1491_CR27","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1109\/TCT.1966.1082620","volume":"13","author":"A Lempel","year":"1966","unstructured":"Lempel A, Cederbaum I (1966) Minimum feedback arc and vertex sets of a directed graph. IEEE Trans Circuit Theory 13(4):399\u2013403","journal-title":"IEEE Trans Circuit Theory"},{"key":"1491_CR28","unstructured":"Maaroju N (2009) Choosing the best heuristic for a NP-Problem. PhD thesis"},{"issue":"2","key":"1491_CR29","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0166-218X(86)90058-2","volume":"14","author":"F Maffioli","year":"1986","unstructured":"Maffioli F (1986) Randomized algorithms in combinatorial optimization: a survey. Discret Appl Math 14(2):157\u2013170","journal-title":"Discret Appl Math"},{"issue":"1","key":"1491_CR30","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1111\/j.1467-8640.1985.tb00058.x","volume":"1","author":"MH Romanycia","year":"1985","unstructured":"Romanycia MH, Pelletier FJ (1985) What is a heuristic? Comput Intell 1(1):47\u201358","journal-title":"Comput Intell"},{"key":"1491_CR31","doi-asserted-by":"publisher","DOI":"10.1002\/9781118631980","volume-title":"Simulation and the Monte Carlo method","author":"RY Rubinstein","year":"2016","unstructured":"Rubinstein RY, Kroese DP (2016) Simulation and the Monte Carlo method. Wiley, Hoboken, NJ"},{"issue":"1","key":"1491_CR32","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1109\/101.17235","volume":"5","author":"RA Rutenbar","year":"1989","unstructured":"Rutenbar RA (1989) Simulated annealing algorithms: an overview. IEEE Circuits Devices Mag 5(1):19\u201326","journal-title":"IEEE Circuits Devices Mag"},{"key":"1491_CR33","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1023\/A:1011315014322","volume":"3","author":"Y Saab","year":"2001","unstructured":"Saab Y (2001) A fast and effective algorithm for the feedback arc set problem. J Heuristics 3:235\u2013250. https:\/\/doi.org\/10.1023\/A:1011315014322","journal-title":"J Heuristics"},{"issue":"3","key":"1491_CR34","doi-asserted-by":"publisher","first-page":"133","DOI":"10.14778\/3021924.3021930","volume":"10","author":"M Simpson","year":"2016","unstructured":"Simpson M, Srinivasan V, Thomo A (2016) Efficient computation of feedback arc set at web-scale. Proc VLDB Endow 10(3):133\u2013144","journal-title":"Proc VLDB Endow"},{"key":"1491_CR35","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2024.106724","volume":"169","author":"Z Xiong","year":"2024","unstructured":"Xiong Z, Zhou Y, Xiao M, Khoussainov B (2024) Finding small feedback arc sets on large graphs. Comput Oper Res 169:106724","journal-title":"Comput Oper Res"},{"issue":"2","key":"1491_CR36","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1109\/TCT.1963.1082116","volume":"10","author":"D Younger","year":"1963","unstructured":"Younger D (1963) Minimum feedback arc sets for a directed graph. IEEE Trans Circuit Theory 10(2):238\u2013245","journal-title":"IEEE Trans Circuit Theory"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-025-01491-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13278-025-01491-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-025-01491-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:29:24Z","timestamp":1765960164000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13278-025-01491-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,12]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["1491"],"URL":"https:\/\/doi.org\/10.1007\/s13278-025-01491-2","relation":{},"ISSN":["1869-5469"],"issn-type":[{"type":"electronic","value":"1869-5469"}],"subject":[],"published":{"date-parts":[[2025,7,12]]},"assertion":[{"value":"18 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 June 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"68"}}