{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:50:57Z","timestamp":1780822257935,"version":"3.54.1"},"reference-count":38,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T00:00:00Z","timestamp":1765238400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:title>ABSTRACT<\/jats:title>\n                  <jats:p>\n                    The\n                    <jats:italic>inversion<\/jats:italic>\n                    of a set  of vertices in a digraph  consists of reversing the direction of all arcs of . We study  (resp., ) which is (for some positive integer ) the minimum number of inversions needed to transform  into a \u2010arc\u2010strong (resp., \u2010strong) digraph or  if no such transformation exists. Note that . We set . We show the following results where  is a fixed integer for :\n                    <jats:list list-type=\"explicit-label\">\n                      <jats:list-item>\n                        <jats:p>for every ;<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>for any fixed positive integer , deciding whether a given oriented graph  with  satisfies  is NP\u2010complete;<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>for any fixed positive integer , deciding whether a given oriented graph  with  satisfies  is NP\u2010complete;<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>if  is a tournament of order at least , then , and ;<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>for some tournament  of order ;<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>if  is a tournament of order at least  (resp., ), then  (resp., );<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>for every , there exists  such that for every positive integer  and every tournament  on at least  vertices, we have .<\/jats:p>\n                      <\/jats:list-item>\n                    <\/jats:list>\n                  <\/jats:p>","DOI":"10.1002\/jgt.23290","type":"journal-article","created":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T06:09:51Z","timestamp":1765346991000},"page":"31-62","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Minimum Number of Inversions to Make a Digraph k\u2010(Arc\u2010)Strong"],"prefix":"10.1002","volume":"111","author":[{"given":"Julien","family":"Duron","sequence":"first","affiliation":[{"name":"Institute of Informatics University of Warsaw Warsaw Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3447-8112","authenticated-orcid":false,"given":"Fr\u00e9d\u00e9ric","family":"Havet","sequence":"additional","affiliation":[{"name":"CNRS, Inria, I3S, Sophia Antipolis Universit\u00e9 C\u00f4te d'Azur Nice France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5410-613X","authenticated-orcid":false,"given":"Florian","family":"H\u00f6rsch","sequence":"additional","affiliation":[{"name":"CISPA Saarbr\u00fccken Saarbr\u00fccken Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cl\u00e9ment","family":"Rambaud","sequence":"additional","affiliation":[{"name":"CNRS, Inria, I3S, Sophia Antipolis Universit\u00e9 C\u00f4te d'Azur Nice France"},{"name":"DIENS, \u00c9cole normale sup\u00e9rieure, CNRS PSL University Paris France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2025,12,9]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-998-1"},{"key":"e_1_2_9_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90060-6"},{"key":"e_1_2_9_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_9_5_1","first-page":"14","volume-title":"Proceedings of the 4th International IPCO Conference on Integer Programming and Combinatorial Optimization, Copenhagen, Denmark, May 29\u201331, 1995, Lecture Notes in Computer Science","author":"Even G.","year":"1995"},{"key":"e_1_2_9_6_1","unstructured":"V.Kann \u201cOn the Approximability of NP\u2010Complete Optimization Problems\u201d (PhD thesis Department of Numerical Analysis and Computing Science Royal Institute of Technology Stockholm 1992)."},{"key":"e_1_2_9_7_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"key":"e_1_2_9_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007887"},{"key":"e_1_2_9_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250806"},{"key":"e_1_2_9_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2010.06.022"},{"issue":"2","key":"e_1_2_9_13_1","article-title":"On the Inversion Number of Oriented Graphs","volume":"23","author":"Bang\u2010Jensen J.","year":"2022","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"issue":"2","key":"e_1_2_9_14_1","article-title":"On the Boolean Dimension of a Graph and Other Related Parameters","volume":"23","author":"Thatte B.","year":"2022","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"e_1_2_9_15_1","doi-asserted-by":"publisher","DOI":"10.37236\/12983"},{"key":"e_1_2_9_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1547135"},{"key":"e_1_2_9_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/2303897"},{"key":"e_1_2_9_18_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1960-049-6"},{"key":"e_1_2_9_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00438-4"},{"key":"e_1_2_9_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.07.004"},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114097"},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.07.001"},{"key":"e_1_2_9_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22900"},{"key":"e_1_2_9_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_2_9_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209016"},{"key":"e_1_2_9_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90024-2"},{"key":"e_1_2_9_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103436"},{"key":"e_1_2_9_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71840-8_2"},{"key":"e_1_2_9_29_1","volume-title":"Flows in Networks","author":"Ford L. R.","year":"2010"},{"key":"e_1_2_9_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0"},{"key":"e_1_2_9_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.01.002"},{"key":"e_1_2_9_32_1","unstructured":"F.Havet F.H\u00f6rsch andC.Rambaud \u201cDiameter of the Inversion Graph \u201darXiv:2405.04119(2024)."},{"key":"e_1_2_9_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010208"},{"key":"e_1_2_9_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_9_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892074"},{"issue":"21","key":"e_1_2_9_36_1","first-page":"2151","article-title":"Chemins Et Circuits Hamiltoniens Des Graphes Complets","volume":"249","author":"Camion P.","year":"1959","journal-title":"Comptes rendus hebdomadaires des s\u00e9ances de l'acad\u00e9mie des sciences"},{"key":"e_1_2_9_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128671"},{"key":"e_1_2_9_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020544"},{"key":"e_1_2_9_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.23290","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T16:18:47Z","timestamp":1765988327000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.23290"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,9]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["10.1002\/jgt.23290"],"URL":"https:\/\/doi.org\/10.1002\/jgt.23290","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,9]]},"assertion":[{"value":"2024-05-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}