{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:15Z","timestamp":1784568315173,"version":"3.55.0"},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2013,9,12]],"date-time":"2013-09-12T00:00:00Z","timestamp":1378944000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>A <jats:italic>minimum feedback arc set<\/jats:italic> of a directed graph <jats:italic>G<\/jats:italic> is a smallest set of arcs whose removal makes <jats:italic>G<\/jats:italic> acyclic. Its cardinality is denoted by \u03b2(<jats:italic>G<\/jats:italic>). We show that a simple Eulerian digraph with <jats:italic>n<\/jats:italic> vertices and <jats:italic>m<\/jats:italic> arcs has \u03b2(<jats:italic>G<\/jats:italic>) \u2265 <jats:italic>m<\/jats:italic><jats:sup>2<\/jats:sup>\/2<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>+<jats:italic>m<\/jats:italic>\/2<jats:italic>n<\/jats:italic>, and this bound is optimal for infinitely many <jats:italic>m, n<\/jats:italic>. Using this result we prove that a simple Eulerian digraph contains a cycle of length at most 6<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>\/<jats:italic>m<\/jats:italic>, and has an Eulerian subgraph with minimum degree at least <jats:italic>m<\/jats:italic><jats:sup>2<\/jats:sup>\/24<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>. Both estimates are tight up to a constant factor. Finally, motivated by a conjecture of Bollob\u00e1s and Scott, we also show how to find long cycles in Eulerian digraphs.<\/jats:p>","DOI":"10.1017\/s0963548313000394","type":"journal-article","created":{"date-parts":[[2013,9,12]],"date-time":"2013-09-12T09:12:54Z","timestamp":1378977174000},"page":"859-873","source":"Crossref","is-referenced-by-count":8,"title":["Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs"],"prefix":"10.1017","volume":"22","author":[{"given":"HAO","family":"HUANG","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"JIE","family":"MA","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ASAF","family":"SHAPIRA","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"BENNY","family":"SUDAKOV","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"RAPHAEL","family":"YUSTER","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2013,9,12]]},"reference":[{"key":"S0963548313000394_ref4","first-page":"181","article-title":"On minimal digraphs with given girth","volume":"XXI","author":"Caccetta","year":"1978","journal-title":"Proc. 9th Southeastern Conference on Combinatorics, Graph Theory, and Computing: Boca Raton 1978. Congress. Numer."},{"key":"S0963548313000394_ref12","unstructured":"Sullivan B. A summary of results and problems related to the Caccetta\u2013H\u00e4ggkvist conjecture. http:\/\/arxiv.org\/abs\/math\/0605646v1"},{"key":"S0963548313000394_ref2","volume-title":"Graduate Texts in Mathematics","author":"Bollob\u00e1s","year":"1998"},{"key":"S0963548313000394_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2331-z"},{"key":"S0963548313000394_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"key":"S0963548313000394_ref11","unstructured":"Sullivan B. (2008) Extremal problems in digraphs. PhD thesis, Princeton University."},{"key":"S0963548313000394_ref9","unstructured":"Nathanson M. The Caccetta\u2013H\u00e4ggkvist conjecture and additive number theory. www.aimath.org\/preprints.html"},{"key":"S0963548313000394_ref3","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0021"},{"key":"S0963548313000394_ref10","volume-title":"The Logical Design of Operating Systems","author":"Shaw","year":"1974"},{"key":"S0963548313000394_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990460"},{"key":"S0963548313000394_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007887"},{"key":"S0963548313000394_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759032"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000394","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T19:20:05Z","timestamp":1556047205000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000394\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,12]]},"references-count":12,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["S0963548313000394"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000394","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,12]]}}}