{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T06:51:32Z","timestamp":1778309492584,"version":"3.51.4"},"reference-count":39,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T00:00:00Z","timestamp":1753833600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100020038","name":"Ny Carlsbergfondet","doi-asserted-by":"publisher","award":["CF21\u20100302"],"award-info":[{"award-number":["CF21\u20100302"]}],"id":[{"id":"10.13039\/100020038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["W1230"],"award-info":[{"award-number":["W1230"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>ABSTRACT<\/jats:title>\n                  <jats:p>We introduce a new bilevel version of the classic shortest path problem and completely characterize its computational complexity with respect to several problem variants. In our problem, the leader and the follower each control a subset of the edges of a graph and together aim at building a path between two given vertices, while each of the two players minimizes the cost of the resulting path according to their own cost function. We investigate both directed and undirected graphs, as well as the special case of directed acyclic graphs. Moreover, we distinguish two versions of the follower's problem: Either they have to complete the edge set selected by the leader such that the joint solution is exactly a path or they have to complete the edge set selected by the leader such that the joint solution is a superset of a path. In general, the bilevel problem turns out to be much harder in the former case: We show that the follower's problem is already NP\u2010hard here and that the leader's problem is even hard for the second level of the polynomial hierarchy, while both problems are one level easier in the latter case. Interestingly, for directed acyclic graphs, this difference turns around, as we give a polynomial\u2010time algorithm for the first version of the bilevel problem, but it stays NP\u2010hard in the second case. Finally, we consider restrictions that render the problem tractable. We prove that, for a constant number of leader's edges, one of our problem variants is actually equivalent to the shortest\u2010\u2010cycle problem, which is a known combinatorial problem with partially unresolved complexity status. In particular, our problem admits a polynomial\u2010time randomized algorithm that can be derandomized if and only if the shortest\u2010\u2010cycle problem admits a deterministic polynomial\u2010time algorithm.<\/jats:p>","DOI":"10.1002\/net.70002","type":"journal-article","created":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T05:46:31Z","timestamp":1753940791000},"page":"428-445","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Complexity of the Bilevel Shortest Path Problem"],"prefix":"10.1002","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9190-642X","authenticated-orcid":false,"given":"Dorothee","family":"Henke","sequence":"first","affiliation":[{"name":"Chair of Business Decisions and Data Science University of Passau  Passau Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7139-4092","authenticated-orcid":false,"given":"Lasse","family":"Wulf","sequence":"additional","affiliation":[{"name":"Section for Algorithms, Logic and Graphs Technical University of Denmark  Kongens Lyngby Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2025,7,30]]},"reference":[{"key":"e_1_2_9_2_1","unstructured":"Y.BeckandM.Schmidt \u201cA Gentle and Incomplete Introduction to Bilevel Optimization \u201d(2021) https:\/\/optimization\u2010online.org\/?p=17182."},{"key":"e_1_2_9_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479\u2010007\u20100176\u20102"},{"key":"e_1_2_9_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-52119-6_20"},{"key":"e_1_2_9_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45827-3"},{"key":"e_1_2_9_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0913069"},{"key":"e_1_2_9_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586088"},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10288\u2010021\u201000477\u2010y"},{"key":"e_1_2_9_9_1","unstructured":"C.Gr\u00fcneandL.Wulf \u201cCompleteness in the Polynomial Hierarchy for Many Natural Problems in Bilevel and Robust Optimization \u201d2024arXiv: 2311.10540 [cs.CC]."},{"key":"e_1_2_9_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.139"},{"key":"e_1_2_9_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.12.1608"},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.08.064"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479\u2010015\u20102016\u20100"},{"key":"e_1_2_9_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-25592-3_7"},{"key":"e_1_2_9_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.5.771.10607"},{"key":"e_1_2_9_16_1","unstructured":"E.LeyandM.Merkert \u201cSolution Methods for Partial Inverse Combinatorial Optimization Problems in Which Weights Can Only be Increased \u201d(2024) https:\/\/optimization\u2010online.org\/?p=25609."},{"key":"e_1_2_9_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167\u20106377(89)90003\u20105"},{"key":"e_1_2_9_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10039"},{"key":"e_1_2_9_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167\u20106377(89)90065\u20105"},{"key":"e_1_2_9_20_1","unstructured":"D.Henke \u201cThe Robust Bilevel Selection Problem \u201d2024arXiv: 2401.03951 [math.OC]."},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/130906593"},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.1155\/2012\/504713"},{"key":"e_1_2_9_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.22111"},{"key":"e_1_2_9_24_1","volume-title":"Maximal spannende Baumprobleme mit einer Hierarchie von zwei Entscheidungstr\u00e4gern","author":"Gassner E.","year":"2002"},{"key":"e_1_2_9_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532\u2010022\u201000227\u2010z"},{"key":"e_1_2_9_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21881"},{"key":"e_1_2_9_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10288\u2010021\u201000499\u20106"},{"key":"e_1_2_9_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10288\u2010009\u20100098\u20108"},{"key":"e_1_2_9_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.08.003"},{"key":"e_1_2_9_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.01.024"},{"key":"e_1_2_9_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_9_32_1","volume-title":"Computers and Intractability","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_9_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.DAM.2023.10.018"},{"key":"e_1_2_9_34_1","doi-asserted-by":"crossref","unstructured":"M.Jackiewicz A.Kasperski andP.Zieli\u00f1ski \u201cComputational Complexity of the Recoverable Robust Shortest Path Problem With Discrete Recourse \u201d2024arXiv: 2403.20000 [cs.CC].","DOI":"10.1016\/j.dam.2025.03.004"},{"key":"e_1_2_9_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304\u20103975(76)90061\u2010X"},{"key":"e_1_2_9_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304\u20103975(76)90062\u20101"},{"key":"e_1_2_9_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304\u20103975(80)90009\u20102"},{"key":"e_1_2_9_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304\u20103975(80)90009\u20102"},{"key":"e_1_2_9_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68891-4_26"},{"key":"e_1_2_9_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/147\/45"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.70002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T17:08:05Z","timestamp":1762016885000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.70002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,30]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1002\/net.70002"],"URL":"https:\/\/doi.org\/10.1002\/net.70002","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,30]]},"assertion":[{"value":"2024-12-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}