{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T03:48:34Z","timestamp":1777002514908,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T00:00:00Z","timestamp":1728950400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T00:00:00Z","timestamp":1728950400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004505","name":"Universit\u00e0 degli Studi di Catania","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004505","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a directed graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$G=(V,A)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we tackle the Minimum Feedback Arc Set (MFAS) Problem by designing an efficient algorithm to search for minimal and stable Feedback Arc Sets, i.e. such that none of the arcs can be reintroduced in the graph without disrupting acyclicity and such that for each vertex the number of eliminated outgoing (resp. incoming) arcs is not bigger than the number of remaining incoming (resp. outgoing) arcs. Our algorithm has a good polynomial upper bound and can therefore be applied even on large graphs. We also introduce an algorithm to generate strongly connected graphs with a known upper bound on their feedback arc set, and on such graphs we test our algorithm.<\/jats:p>","DOI":"10.1007\/s10878-024-01209-8","type":"journal-article","created":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T15:28:04Z","timestamp":1729006084000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient heuristics to compute minimal and stable feedback arc sets"],"prefix":"10.1007","volume":"48","author":[{"given":"Claudia","family":"Cavallaro","sequence":"first","affiliation":[]},{"given":"Vincenzo","family":"Cutello","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3421-3293","authenticated-orcid":false,"given":"Mario","family":"Pavone","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,15]]},"reference":[{"key":"1209_CR1","doi-asserted-by":"crossref","unstructured":"Alpert CJ (1998) The ispd98 circuit benchmark suite. In: Proceedings of the 1998 international symposium on physical design (New York, NY, USA, 1998), ISPD \u201998, Association for Computing Machinery. pp\u00a080\u201385","DOI":"10.1145\/274535.274546"},{"key":"1209_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. ACM J Exp Algorithmics 26:1\u201328","journal-title":"ACM J Exp Algorithmics"},{"key":"1209_CR3","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 (USA, 1990), SODA \u201990, Society for Industrial and Applied Mathematics. pp\u00a0236-243"},{"key":"1209_CR4","unstructured":"Cavallaro C, Cutello V, Pavone M (2023) Effective heuristics for finding small minimal feedback arc set even for large graphs. In: CEUR Workshop Proceedings. vol.\u00a03606"},{"key":"1209_CR5","unstructured":"Cavallaro C, Cutello V, Pavone M (2024) Efficient vertex linear orderings to find minimal feedback arc sets (minfas). In: Proceedings of the 18th learning and intelligent optimization conference. Lecture Notes in Computer Science, vol. 14990"},{"key":"1209_CR6","volume-title":"Introduction to algorithms","author":"T Cormen","year":"2022","unstructured":"Cormen T, Leiserson C, Rivest R, Stein C (2022) Introduction to algorithms, 4th edn. MIT Press, Cambridge","edition":"4"},{"key":"1209_CR7","doi-asserted-by":"crossref","unstructured":"Cutello V, Oliva M, Pavone M, Scollo RA (2019) An immune metaheuristics for large instances of the weighted feedback vertex set problem. In: 2019 IEEE symposium series on computational intelligence (SSCI). pp.\u00a01928\u20131936","DOI":"10.1109\/SSCI44817.2019.9002988"},{"key":"1209_CR8","first-page":"1","volume-title":"Learning and intelligent optimization","author":"V Cutello","year":"2020","unstructured":"Cutello V, Oliva M, Pavone M, Scollo RA (2020) A hybrid immunological search for the weighted feedback vertex set problem. In: Matsatsinis NF, Marinakis Y, Pardalos P (eds) Learning and intelligent optimization. Springer, Cham, pp 1\u201316"},{"key":"1209_CR9","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-319-22180-9_18","volume-title":"Intelligent computing theories and methodologies","author":"V Cutello","year":"2015","unstructured":"Cutello V, Pappalardo F (2015) Targeting the minimum vertex set problem with an enhanced genetic algorithm improved with local search strategies. In: Huang D-S, Bevilacqua V, Premaratne P (eds) Intelligent computing theories and methodologies. Springer, Cham, pp 177\u2013188"},{"issue":"16","key":"1209_CR10","doi-asserted-by":"publisher","first-page":"2389","DOI":"10.1016\/j.dam.2012.06.004","volume":"160","author":"J Darlay","year":"2012","unstructured":"Darlay J, Brauner N, Moncel J (2012) Dense and sparse graph partition. Discr Appl Math 160(16):2389\u20132396","journal-title":"Discr Appl Math"},{"issue":"4","key":"1209_CR11","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/1027084.1027085","volume":"9","author":"A Dasdan","year":"2004","unstructured":"Dasdan A (2004) Experimental analysis of the fastest optimum cycle ratio and mean algorithms. ACM Trans Des Autom Electron Syst 9(4):385\u2013418","journal-title":"ACM Trans Des Autom Electron Syst"},{"issue":"1","key":"1209_CR12","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162(1):439\u2013485","journal-title":"Ann Math"},{"issue":"6","key":"1209_CR13","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 W (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":"1209_CR14","doi-asserted-by":"crossref","unstructured":"Gupte M, Shankar P, Li J, Muthukrishnan S, Iftode L (2011) Finding hierarchy in directed online social networks. In: Proceedings of the 20th international conference on World Wide Web (New York, NY, USA), WWW \u201911, Association for Computing Machinery. pp\u00a0557\u2013566","DOI":"10.1145\/1963405.1963484"},{"key":"1209_CR15","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":"1209_CR16","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. ACM J Exp Algorithmics 26:1\u20139","journal-title":"ACM J Exp Algorithmics"},{"key":"1209_CR17","volume-title":"Advances in neural information processing systems","author":"R Herbrich","year":"2006","unstructured":"Herbrich R, Minka T, Graepel T (2006) Trueskill\u2122: a Bayesian skill rating system. In: Sch\u00f6lkopf B, Platt J, Hoffman T (eds) Advances in neural information processing systems. MIT Press, Cambridge"},{"key":"1209_CR18","first-page":"85","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. Springer, Boston, pp 85\u2013103"},{"key":"1209_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-10515-9","volume-title":"Feedback arc set: a history of the problem and algorithms","author":"R Kudeli\u0107","year":"2022","unstructured":"Kudeli\u0107 R (2022) Feedback arc set: a history of the problem and algorithms. Springer, Berlin"},{"issue":"3","key":"1209_CR20","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1112\/jlms\/s2-17.3.369","volume":"2","author":"CL Lucchesi","year":"1978","unstructured":"Lucchesi CL, Younger DH (1978) A minimax theorem for directed graphs. J London Math Soc 2(3):369\u2013374","journal-title":"J London Math Soc"},{"issue":"1","key":"1209_CR21","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1093\/bioinformatics\/btr620","volume":"28","author":"N Soranzo","year":"2011","unstructured":"Soranzo N, Ramezani F, Iacono G, Altafini C (2011) Decompositions of large-scale biological systems based on dynamical properties. Bioinformatics 28(1):76\u201383","journal-title":"Bioinformatics"},{"key":"1209_CR22","doi-asserted-by":"crossref","unstructured":"Sun J, Ajwani D, Nicholson PK, Sala A, Parthasarathy S (2017) Breaking cycles in noisy hierarchies. In: Proceedings of the 2017 ACM on web science conference (New York, NY, USA), WebSci \u201917, association for computing machinery. pp\u00a0151\u2013160","DOI":"10.1145\/3091478.3091495"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01209-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01209-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01209-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T11:05:02Z","timestamp":1730977502000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01209-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,15]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1209"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01209-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,15]]},"assertion":[{"value":"22 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"30"}}