Premium
A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths
Author(s) -
Bazgan Cristina,
Fluschnik Till,
Nichterlein André,
Niedermeier Rolf,
Stahlberg Maximilian
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21832
Subject(s) - parameterized complexity , shortest path problem , computer science , undirected graph , robustness (evolution) , computational complexity theory , enhanced data rates for gsm evolution , theoretical computer science , graph , algorithm , combinatorics , mathematics , mathematical optimization , artificial intelligence , biochemistry , chemistry , gene
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.