  We study the NP-hard Shortest Path Most Vital Edges problem arising in the
context of analyzing network robustness. For an undirected graph with positive
integer edge lengths and two designated vertices $s$ and $t$, the goal is to
delete as few edges as possible in order to increase the length of the (new)
shortest $st$-path as much as possible. This scenario has been studied from the
viewpoint of parameterized complexity and approximation algorithms. We
contribute to this line of research by providing refined computational
tractability as well as hardness results. We achieve this by a systematic
investigation of various problem-specific parameters and their influence on the
computational complexity. Charting the border between tractability and
intractability, we also identify numerous challenges for future research.
