# A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths

Preprint · Cristina Bazgan, Till Fluschnik, André Nichterlein, Rolf Niedermeier, Maximilian Stahlberg

- Archive id: arxiv:1804.09155
- Published: 2018-04-24
- arXiv: https://arxiv.org/abs/1804.09155
- Source URL: https://arxiv.org/abs/1804.09155
- PDF: https://arxiv.org/pdf/1804.09155
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.