Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths

Rajesh Chitnis; Samuel Thomas; Anthony Wirth

doi:10.1016/j.tcs.2026.115842

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths

Rajesh Chitnis
, Samuel Thomas^*
, Anthony Wirth

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

Original language	English
Article number	115842
Journal	Theoretical Computer Science
Early online date	2 Mar 2026
DOIs	https://doi.org/10.1016/j.tcs.2026.115842
Publication status	E-pub ahead of print - 2 Mar 2026

Keywords

disjoint shortest paths
directed acyclic graphs
planar graphs
1-planar graphs
exponential time hypothesis
lower bounds
FPT inapproximability

Access to Document

10.1016/j.tcs.2026.115842Licence: Creative Commons: Attribution (CC BY)

Cite this

@article{4ba708f65680435da21f867f3e998b15,

title = "Lower Bounds for Approximate (\& Exact) k-Disjoint-Shortest-Paths",

keywords = "disjoint shortest paths, directed acyclic graphs, planar graphs, 1-planar graphs, exponential time hypothesis, lower bounds, FPT inapproximability",

author = "Rajesh Chitnis and Samuel Thomas and Anthony Wirth",

year = "2026",

month = mar,

day = "2",

doi = "10.1016/j.tcs.2026.115842",

language = "English",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths

AU - Chitnis, Rajesh

AU - Thomas, Samuel

AU - Wirth, Anthony

PY - 2026/3/2

Y1 - 2026/3/2

KW - disjoint shortest paths

KW - directed acyclic graphs

KW - planar graphs

KW - 1-planar graphs

KW - exponential time hypothesis

KW - lower bounds

KW - FPT inapproximability

U2 - 10.1016/j.tcs.2026.115842

DO - 10.1016/j.tcs.2026.115842

M3 - Article

SN - 0304-3975

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 115842

ER -