A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths

作     者：Bazgan, Cristina Fluschnik, Till Nichterlein, Andre Niedermeier, Rolf Stahlberg, Maximilian 

作者机构：PSL Res Univ Univ Paris Dauphine CNRS LAMSADE Paris France Tech Univ Berlin Inst Softwaretech & Theoret Informat Berlin Germany 

出 版 物：《NETWORKS》 (网络)

年 卷 期：2019年第73卷第1期

页      面：23-37页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Deutsche Forschungsgemeinschaft [NI 369/13] Institut Universitaire de France 

主　　题：approximation algorithms interdiction problems length-bounded cuts NP-hardness parameterized complexity special graph classes 

摘      要：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.