{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T07:26:49Z","timestamp":1774078009971,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T00:00:00Z","timestamp":1774051200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T00:00:00Z","timestamp":1774051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["Momentum Programme (LP2021-2)"],"award-info":[{"award-number":["Momentum Programme (LP2021-2)"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We consider the following problem that we call the\n                    <jats:sc>Shortest Two Disjoint Paths<\/jats:sc>\n                    problem: given an undirected graph\u00a0\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$G=(V,E)$$<\/jats:tex-math>\n                        <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>E<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with edge weight function\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$${w:E\\rightarrow \\mathbb {R}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>w<\/mml:mi>\n                            <mml:mo>:<\/mml:mo>\n                            <mml:mi>E<\/mml:mi>\n                            <mml:mo>\u2192<\/mml:mo>\n                            <mml:mi>R<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , two terminals\n                    <jats:italic>s<\/jats:italic>\n                    and\u00a0\n                    <jats:italic>t<\/jats:italic>\n                    in\u00a0\n                    <jats:italic>G<\/jats:italic>\n                    , find two internally vertex-disjoint paths between\n                    <jats:italic>s<\/jats:italic>\n                    and\n                    <jats:italic>t<\/jats:italic>\n                    with minimum total weight. As shown recently by Schlotter and Seb\u0151 (2022), this problem becomes\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\textsf{NP}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>NP<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in\u00a0\n                    <jats:italic>G<\/jats:italic>\n                    with negative total weight. We propose a polynomial-time algorithm that solves the\n                    <jats:sc>Shortest Two Disjoint Paths<\/jats:sc>\n                    problem for conservative weights in the case when the negative-weight edges form a constant number of trees in\u00a0\n                    <jats:italic>G<\/jats:italic>\n                    .\n                  <\/jats:p>","DOI":"10.1007\/s00453-026-01375-7","type":"journal-article","created":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T04:12:50Z","timestamp":1774066370000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Shortest Two Disjoint Paths in Conservative Graphs"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0114-8280","authenticated-orcid":false,"given":"Ildik\u00f3","family":"Schlotter","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,21]]},"reference":[{"key":"1375_CR1","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.jctb.2016.10.001","volume":"122","author":"I Adler","year":"2017","unstructured":"Adler, I., Kolliopoulos, S.G., Krause, P.K., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Irrelevant vertices for the Planar Disjoint Paths problem. Journal of Combinatorial Theory, Series B 122, 815\u2013843 (2017). https:\/\/doi.org\/10.1016\/j.jctb.2016.10.001","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"1375_CR2","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Nanongkai, D., Wulff-Nilsen, C.: Negative-weight single-source shortest paths in near-linear time. In: FOCS 2022: Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science, pp. 600\u2013611. IEEE Computer Society (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00063","DOI":"10.1109\/FOCS54457.2022.00063"},{"issue":"6","key":"1375_CR3","doi-asserted-by":"publisher","first-page":"1698","DOI":"10.1137\/18M1223034","volume":"48","author":"A Bj\u00f6rklund","year":"2019","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Shortest two disjoint paths in polynomial time. SIAM J. Comput. 48(6), 1698\u20131710 (2019). https:\/\/doi.org\/10.1137\/18M1223034","journal-title":"SIAM J. Comput."},{"key":"1375_CR4","doi-asserted-by":"crossref","unstructured":"Busacker, R.G., Gowen, P.J.: A procedure for determining a family of miminum-cost network flow patterns. Technical Report ORO-TP-15, Operations Research Office, Johns Hopkins University (1960)","DOI":"10.21236\/AD0249662"},{"key":"1375_CR5","doi-asserted-by":"publisher","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M.: The planar directed $$k$$-vertex-disjoint paths problem is fixed-parameter tractable. In: FOCS 2013: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 197\u2013206. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.29","DOI":"10.1109\/FOCS.2013.29"},{"issue":"2","key":"1375_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1921659.1921665","volume":"7","author":"\u00c9C Verdi\u00e8re","year":"2011","unstructured":"Verdi\u00e8re, \u00c9.C., Schrijver, A.: Shortest vertex-disjoint two-face paths in planar graphs. ACM Trans. Algorithms 7(2), 19\u201311912 (2011). https:\/\/doi.org\/10.1145\/1921659.1921665","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"1375_CR7","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1137\/0405009","volume":"5","author":"G Ding","year":"1992","unstructured":"Ding, G., Schrijver, A., Seymour, P.D.: Disjoint paths in a planar graph - a general theorem. SIAM J. Discret. Math. 5(1), 112\u2013116 (1992). https:\/\/doi.org\/10.1137\/0405009","journal-title":"SIAM J. Discret. Math."},{"key":"1375_CR8","first-page":"27","volume":"3","author":"M Iri","year":"1960","unstructured":"Iri, M.: A new method for solving transportation-network problems. Journal of the Operations Research Society of Japan 3, 27\u201387 (1960)","journal-title":"Journal of the Operations Research Society of Japan"},{"issue":"4","key":"1375_CR9","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1287\/opre.10.4.476","volume":"10","author":"WS Jewell","year":"1962","unstructured":"Jewell, W.S.: Optimal flow through networks. Oper. Res. 10(4), 476\u2013499 (1962)","journal-title":"Oper. Res."},{"issue":"1","key":"1375_CR10","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5(1), 45\u201368 (1975)","journal-title":"Networks"},{"issue":"4","key":"1375_CR11","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/j.disopt.2010.05.002","volume":"7","author":"Y Kobayashi","year":"2010","unstructured":"Kobayashi, Y., Sommer, C.: On shortest disjoint paths in planar graphs. Discret. Optim. 7(4), 234\u2013245 (2010). https:\/\/doi.org\/10.1016\/j.disopt.2010.05.002","journal-title":"Discret. Optim."},{"key":"1375_CR12","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Misra, P., Pilipczuk, M., Saurabh, S., Zehavi, M.: An exponential time parameterized algorithm for planar disjoint paths. In: STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1307\u20131316. Association for Computing Machinery, New York, NY, USA (2020). https:\/\/doi.org\/10.1145\/3357713.3384250","DOI":"10.1145\/3357713.3384250"},{"key":"1375_CR13","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1061425.1061430","volume":"5","author":"JF Lynch","year":"1975","unstructured":"Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsletter 5, 31\u201336 (1975). https:\/\/doi.org\/10.1145\/1061425.1061430","journal-title":"ACM SIGDA Newsletter"},{"issue":"1","key":"1375_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B 63(1), 65\u2013110 (1995). https:\/\/doi.org\/10.1006\/jctb.1995.1006","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"1375_CR15","unstructured":"Schlotter, I., Sebo, A.: Odd paths, cycles and $$T$$-joins: Connections and algorithms (2022) arXiv:2211.12862 [cs.CC]. To appear in SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"1375_CR16","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1137\/S0097539792224061","volume":"23","author":"A Schrijver","year":"1994","unstructured":"Schrijver, A.: Finding $$k$$ disjoint paths in a directed planar graph. SIAM J. Comput. 23(4), 780\u2013788 (1994). https:\/\/doi.org\/10.1137\/S0097539792224061","journal-title":"SIAM J. Comput."},{"key":"1375_CR17","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01375-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01375-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01375-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T04:12:52Z","timestamp":1774066372000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01375-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,21]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1375"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01375-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,21]]},"assertion":[{"value":"27 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"31"}}