Thumbnail - Request a copy

A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths

Bazgan, Cristina; Nichterlein, André; Niedermeier, Rolf (2015), A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths, in Paschos, Vangelis Th.; Widmayer, Peter, Algorithms and Complexity, Springer : Cham, p. 47-60. 10.1007/978-3-319-18173-8_3

Type
Communication / Conférence
Date
2015
Conference title
9th International Conference - CIAC 2015
Conference date
2015-05
Conference city
Paris
Conference country
France
Book title
Algorithms and Complexity
Book author
Paschos, Vangelis Th.; Widmayer, Peter
Publisher
Springer
Published in
Cham
ISBN
978-3-319-18172-1
Number of pages
430
Pages
47-60
Publication identifier
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Nichterlein, André
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Niedermeier, Rolf
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Abstract (EN)
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.
Subjects / Keywords
shortest path; parameterized complexity
JEL
C44 - Operations Research; Statistical Decision Theory