{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T07:04:19Z","timestamp":1779087859674,"version":"3.51.4"},"reference-count":110,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2021,4,23]],"date-time":"2021-04-23T00:00:00Z","timestamp":1619136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian Research Promotion Agency","award":["846920"],"award-info":[{"award-number":["846920"]}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P27891-N32"],"award-info":[{"award-number":["P27891-N32"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            A feedback arc set of a directed graph\n            <jats:italic>G<\/jats:italic>\n            is a subset of its arcs containing at least one arc of every cycle in\n            <jats:italic>G<\/jats:italic>\n            . Finding a feedback arc set of minimum cardinality is an NP-hard problem called the\n            <jats:italic>minimum feedback arc set problem<\/jats:italic>\n            . Numerically, the minimum set cover formulation of the minimum feedback arc set problem is appropriate as long as all simple cycles in\n            <jats:italic>G<\/jats:italic>\n            can be enumerated. Unfortunately, even those sparse graphs that are important for practical applications often have \u03a9 (2\n            <jats:sup>n<\/jats:sup>\n            ) simple cycles. Here we address precisely such situations: An exact method is proposed for sparse graphs that enumerates simple cycles in a lazy fashion and iteratively extends an incomplete cycle matrix. In all cases encountered so far, only a tractable number of cycles has to be enumerated until a minimum feedback arc set is found. The practical limits of the new method are evaluated on a test set containing computationally challenging sparse graphs, relevant for industrial applications. The 4,468 test graphs are of varying size and density and suitable for testing the scalability of exact algorithms over a wide range.\n          <\/jats:p>","DOI":"10.1145\/3446429","type":"journal-article","created":{"date-parts":[[2021,4,23]],"date-time":"2021-04-23T10:06:43Z","timestamp":1619172403000},"page":"1-28","source":"Crossref","is-referenced-by-count":24,"title":["An Exact Method for the Minimum Feedback Arc Set Problem"],"prefix":"10.1145","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4715-9003","authenticated-orcid":false,"given":"Ali","family":"Baharev","sequence":"first","affiliation":[{"name":"University of Vienna, Wien, Austria"}],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Hermann","family":"Schichl","sequence":"additional","affiliation":[{"name":"University of Vienna, Wien, Austria"}],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Arnold","family":"Neumaier","sequence":"additional","affiliation":[{"name":"University of Vienna, Wien, Austria"}],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Tobias","family":"Achterberg","sequence":"additional","affiliation":[{"name":"Gurobi GmbH, Frankfurt am Main"}],"role":[{"role":"author","vocab":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,23]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-008-0001-1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 1996 37th Annual Symposium on Foundations of Computer Science. 21\u201330","author":"Arora S."},{"key":"e_1_2_1_6_1","volume-title":"Version Number: V7.1.","author":"Technology Aspen","year":"2009"},{"key":"e_1_2_1_7_1","volume-title":"Lecture Notes in Computer Science","volume":"8096","author":"Austrin P."},{"key":"e_1_2_1_8_1","volume-title":"Retrieved","author":"Baharev A.","year":"2019"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0300-9467(72)85030-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","volume-title":"Layered drawings of digraphs","author":"Bastert Oliver","DOI":"10.1007\/3-540-44969-8_5"},{"key":"e_1_2_1_11_1","volume-title":"Shor","author":"Berger Bonnie","year":"1990"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.03.071"},{"key":"e_1_2_1_13_1","volume-title":"Westerberg","author":"Biegler Lorenz T.","year":"1997"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690300412"},{"key":"e_1_2_1_15_1","volume-title":"Technical Report MIP-1104. Department of Informatics and Mathematics","author":"Brandenburg F. J.","year":"2011"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/cite.201700041"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007887"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907)","author":"Charikar M."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690160206"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690150122"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_23_1","volume-title":"Leiserson","author":"Cormen Thomas H.","year":"2009"},{"key":"e_1_2_1_24_1","unstructured":"David Coudert Afonso Ferreira and Xavier Mu\u00f1oz. 1999. OTIS-based multi-hop multi-OPS lightwave networks. In Parallel and Distributed Processing: 11th IPPS\/SPDP\u201999 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing San Juan Puerto Rico USA April 12\u201316 1999 Proceedings. Springer Berlin Germany 897\u2013910.  David Coudert Afonso Ferreira and Xavier Mu\u00f1oz. 1999. OTIS-based multi-hop multi-OPS lightwave networks. In Parallel and Distributed Processing: 11th IPPS\/SPDP\u201999 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing San Juan Puerto Rico USA April 12\u201316 1999 Proceedings. Springer Berlin Germany 897\u2013910."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2.4.393"},{"key":"e_1_2_1_26_1","volume-title":"Dymola\u2014Dynamic Modeling Laboratory: User Manual.","author":"Dassault Syst\u00e8mes AB."},{"key":"e_1_2_1_27_1","volume-title":"Breaking cycles for minimizing crossings. ACM Journal of Experimental Algorithmics 6 (Dec","author":"Demestrescu Camil","year":"2001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00491-X"},{"key":"e_1_2_1_29_1","volume-title":"Graph Theory with Applications to Engineering and Computer Science","author":"Deo Narsingh"},{"key":"e_1_2_1_30_1","volume-title":"Computer-Aided Chemical Engineering","volume":"35","author":"Dimian A. C."},{"key":"e_1_2_1_31_1","unstructured":"R. G. Downey and M. R. Fellows. 2013. In Fundamentals of Parameterized Complexity D. Gries and F. B. Schneider (Eds.). Springer-Verlag London UK.  R. G. Downey and M. R. Fellows. 2013. In Fundamentals of Parameterized Complexity D. Gries and F. B. Schneider (Eds.). Springer-Verlag London UK."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180105"},{"key":"e_1_2_1_33_1","first-page":"15","article-title":"A new heuristic for the feedback arc set problem","volume":"35","author":"Eades P.","year":"1995","journal-title":"Australasian Journal of Combinatorics"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90079-O"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I","volume":"6","author":"Erd\u0151s P.","year":"1959","journal-title":"Publicationes Mathematicae"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"F. V. Fomin and D. Kratsch. 2010. Measure and conquer. In Exact Exponential Algorithms. Springer Berlin Germany 101\u2013124.  F. V. Fomin and D. Kratsch. 2010. Measure and conquer. In Exact Exponential Algorithms. Springer Berlin Germany 101\u2013124.","DOI":"10.1007\/978-3-642-16533-7_6"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.5.1.97"},{"key":"e_1_2_1_39_1","unstructured":"R. S. Garfinkel and G. L. Nemhauser. 1972. Integer Programming. Wiley New York NY.  R. S. Garfinkel and G. L. Nemhauser. 1972. Integer Programming. Wiley New York NY."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690210403"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706098"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.8.1190"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.6.1195"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel M. J\u00fcnger and G. Reinelt. 1985. Acyclic Subdigraphs and Linear Orderings: Polytopes Facets and a Cutting Plane Algorithm. Springer Dordrecht Netherlands 217\u2013264. DOI:https:\/\/doi.org\/10.1007\/978-94-009-5315-4_7  M. Gr\u00f6tschel M. J\u00fcnger and G. Reinelt. 1985. Acyclic Subdigraphs and Linear Orderings: Polytopes Facets and a Cutting Plane Algorithm. Springer Dordrecht Netherlands 217\u2013264. DOI:https:\/\/doi.org\/10.1007\/978-94-009-5315-4_7","DOI":"10.1007\/978-94-009-5315-4_7"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582009"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1971.1083332"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.4173\/mic.1983.3.2"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690200231"},{"key":"e_1_2_1_50_1","volume-title":"Inc.","year":"2014"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756144"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 2008 IEEE 49th Annual Symposium on Foundations of Computer Science (FOCS\u201908)","author":"Guruswami V."},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 7th Python in Science Conference (SciPy\u201908)","author":"Hagberg Aric A."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9777-6"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(79)80057-5"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(77)80011-2"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675809"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676323"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1002\/scj.4690170803"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-9-424"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the AIChE 68th National Meeting.","author":"Jain Y. V. S."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204007"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804034"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(81)90005-9"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45172-3_9"},{"key":"e_1_2_1_67_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M."},{"key":"e_1_2_1_69_1","first-page":"577","article-title":"Mathematics without numbers","volume":"88","author":"Kemeny John G.","year":"1959","journal-title":"Daedalus"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250806"},{"key":"e_1_2_1_71_1","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902)","author":"Khot Subhash","year":"2002"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690120613"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690120625"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1021\/ie50269a005"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30141-7_45"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-17.3.369"},{"key":"e_1_2_1_80_1","volume-title":"Computation sequence in process flowsheet calculations","author":"Mah Richard S. H."},{"key":"e_1_2_1_81_1","volume-title":"The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization. Applied Mathematical Sciences","author":"Mart\u00ed Rafael"},{"key":"e_1_2_1_82_1","volume-title":"Blair","author":"Miller Ronald E.","year":"2009"},{"key":"e_1_2_1_83_1","volume-title":"Applied Optimization","volume":"33","author":"Mitchell J. E."},{"key":"e_1_2_1_84_1","volume-title":"Retrieved","year":"2018"},{"key":"e_1_2_1_85_1","volume-title":"Retrieved","author":"Modelon","year":"2018"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(88)85006-3"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690270504"},{"key":"e_1_2_1_88_1","volume-title":"Retrieved","year":"2018"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993315"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_91_1","volume-title":"Proceedings of the 1992 IEEE International Symposium on Circuits and Systems (ISCAS\u201992)","volume":"4","author":"Park S.","year":"1863"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690190614"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90022-3"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.05.014"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1334-2"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1080\/00986449708936616"},{"key":"e_1_2_1_97_1","unstructured":"D. K. Pradhan S. M. Reddy and J. G. Kuhl. 1980. Directed Graphs with Minimal Diameter and Maximal Connectivity. Technical Report. School of Engineering Oakland University RochesterMI.  D. K. Pradhan S. M. Reddy and J. G. Kuhl. 1980. Directed Graphs with Minimal Diameter and Maximal Connectivity. Technical Report. School of Engineering Oakland University RochesterMI."},{"key":"e_1_2_1_98_1","volume-title":"Lecture Notes in Computer Science","volume":"7408","author":"Saket R."},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00270-9"},{"key":"e_1_2_1_100_1","series-title":"Lecture Notes in Mathematics","volume-title":"Numerical Analysis","author":"Sargent R. W. H."},{"key":"e_1_2_1_101_1","first-page":"190","article-title":"Speed-up in chemical engineering design","volume":"42","author":"Sargent R. W. H.","year":"1964","journal-title":"Transactions of the Institution of Chemical Engineers"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00339-5"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/48.3-4.303"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690250406"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1016\/0009-2509(74)80095-3"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(84)80011-3"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308636"},{"key":"e_1_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1021\/ie50279a011"},{"key":"e_1_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690180312"},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(93)80026-J"},{"key":"e_1_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.1016\/0300-9467(71)87003-X"},{"key":"e_1_2_1_116_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.074492.107"},{"key":"e_1_2_1_117_1","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(88)87007-8"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446429","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3446429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:27Z","timestamp":1750191447000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,23]]},"references-count":110,"alternative-id":["10.1145\/3446429"],"URL":"https:\/\/doi.org\/10.1145\/3446429","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,23]]}}}