LAUSR

In this paper we study the most vital vertices for the shortest s–t path problem. This problem consists, given a digraph $$D=(V\cup \{s,t\},A)$$D=(V∪{s,t},A) and a threshold $$d\in \mathbb {N}$$d∈N, in finding the minimum number of nodes to delete from D in such a way that there does not exist a s–t path of length less or equal than d. We prove the NP-hardness of this problem and propose an integer linear program using an exponential number of inequalities. We investigate the facial structure of the associated polytope. We prove that this polytope is integer and we derive an efficient Branch-and-Cut algorithm. Finally, we present and discuss some computational results.