A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
Dr. rer. nat. André Nichterlein (TU Berlin)
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 mostly studied from the viewpoint of
approximation algorithms and heuristics, while we particularly
introduce a parameterized and multivariate point of view. We derive
refined tractability as well as hardness results, and identify
numerous directions for future research. Among other things, we show
that increasing the shortest path length by at least one is much
easier than to increase it by at least two.
Back to the research colloquium site.