{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:52:06Z","timestamp":1787320326399,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2154082"],"award-info":[{"award-number":["DMS-2154082"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/X013642\/1"],"award-info":[{"award-number":["EP\/X013642\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018267"],"award-info":[{"award-number":["2018267"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>For an oriented graph [Formula: see text] and a set [Formula: see text], the inversion of [Formula: see text] in [Formula: see text] is the digraph obtained by reversing the orientations of the edges of [Formula: see text] with both endpoints in [Formula: see text]. The inversion number of [Formula: see text], [Formula: see text], is the minimum number of inversions which can be applied in turn to [Formula: see text] to produce an acyclic digraph. Answering a recent question of Bang-Jensen, da Silva, and Havet we show that, for each [Formula: see text] and tournament [Formula: see text], the problem of deciding whether [Formula: see text] is solvable in time [Formula: see text], which is tight for all [Formula: see text]. In particular, the problem is fixed-parameter tractable when parameterized by [Formula: see text]. On the other hand, we build on their work to prove their conjecture that for [Formula: see text] the problem of deciding whether a general oriented graph [Formula: see text] has [Formula: see text] is NP-complete. We also construct oriented graphs with inversion number equal to twice their cycle transversal number, confirming another conjecture of Bang-Jensen, da Silva, and Havet, and we provide a counterexample to their conjecture concerning the inversion number of so-called dijoin digraphs while proving that it holds in certain cases. Finally, we asymptotically solve the natural extremal question in this setting, improving on previous bounds of Belkhechine, Bouaziz, Boudabbous, and Pouzet to show that the maximum inversion number of an [Formula: see text]-vertex tournament is [Formula: see text].<\/jats:p>","DOI":"10.1137\/23m1547135","type":"journal-article","created":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T19:20:58Z","timestamp":1705519258000},"page":"327-347","source":"Crossref","is-referenced-by-count":6,"title":["Invertibility of Digraphs and Tournaments"],"prefix":"10.1137","volume":"38","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Department of Mathematics, Princeton University, Princeton, NJ 08544 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emil","family":"Powierski","sequence":"additional","affiliation":[{"name":"Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9446-8162","authenticated-orcid":true,"given":"Michael","family":"Savery","sequence":"additional","affiliation":[{"name":"Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK."},{"name":"Heilbronn Institute for Mathematical Research, Bristol BS8 1UG, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[{"name":"Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elizabeth","family":"Wilmer","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Oberlin College, Oberlin, OH 44074 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,1,16]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"key":"ref2","unstructured":"G. Aubian , \nF. Havet , \nF. H\u00f6rsch , \nF. Klingelhoefer , \nN. Nisse , \nC. Rambaud , and \nQ. Vermande  , Problems, Proofs, and Disproofs on the Inversion Number, preprint, https:\/\/doi.org\/10.48550\/arxiv.2212.09188, 2022."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250627"},{"key":"ref4","volume":"23","author":"Bang-Jensen J.","year":"2022","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"ref5","unstructured":"H. Belkhechine  , Ind\u00e9composabilit\u00e9 des graphes et des tournois, Ph.D. thesis, Universit\u00e9 Claude Bernard - Lyon I; Universit\u00e9 de Sfax, Facult\u00e9 des sciences, 2009, https:\/\/tel.archives-ouvertes.fr\/tel-00609544."},{"key":"ref6","unstructured":"H. Belkhechine , \nM. Bouaziz , \nI. Boudabbous , and \nM. Pouzet  , Inversions in Tournaments, Unpublished."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2010.06.022"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1969-059-3"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"A. Caprara  , Sorting by reversals is difficult, in Proceedings of the First Annual International Conference on Computational Molecular Biology (RECOMB \u201997), ACM, New York, 1997, pp. 75\u201383, https:\/\/doi.org\/10.1145\/267521.267531.","DOI":"10.1145\/267521.267531"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007887"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"J. Chen , \nY. Liu , \nS. Lu , \nB. O\u2019sullivan , and \nI. Razgon  , A fixed-parameter algorithm for the directed feedback vertex set problem, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 2008, pp. 177\u2013186.","DOI":"10.1145\/1374376.1374404"},{"key":"ref12","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90060-6"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262062824.001.0001"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"ref17","first-page":"25","volume-title":"Perfect Graphs","author":"Gallai T.","year":"2001"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(75)90003-8"},{"key":"ref19","unstructured":"S. Hannenhalli  and \nP. Pevzner  , To cut.or not to cut (applications of comparative physical maps in molecular evolution), in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201996), ACM, New York, SIAM, Philadelphia, 1996, pp. 304\u2013313, https:\/\/dl.acm.org\/doi\/10.5555\/313852.314077."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300516"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"R. M. Karp  , Reducibility among combinatorial problems, in Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations,  \nR. E. Miller , \nJ. W. Thatcher , and \nJ. D. Bohlinger  , eds. Springer New York, 1972, pp. 85\u2013103, https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-10515-9"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10081"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1969.12000160"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/0401037"},{"key":"ref26","volume":"23","author":"Pouzet M.","year":"2022","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010204"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02017965"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1547135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:56:51Z","timestamp":1787317011000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1547135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,16]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/23M1547135"],"URL":"https:\/\/doi.org\/10.1137\/23m1547135","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,16]]}}}