Inapproximability bounds for shortest-path network intediction problems

We consider two network interdiction problems: one where a network user tries to traverse a network from a starting vertex s to a target vertex t along the shortest path while an interdictor tries to eliminate all short s-t paths by destroying as few vertices (arcs) as possible, and one where the network user, as before, tries to traverse the network from s to t along the shortest path while the interdictor tries to destroy a fixed number of vertices (arcs) so as to cause the biggest increase in the shortest s-t path. The latter problem is known as the Most Vital Vertices (Arcs) Problem. In this paper we provide inapproximability bounds for several variants of these problems