Blocking Shortest Paths between Three Terminals Is NP-Hard: A Reduction from Three-Terminal Cut

In the problem Blocking Shortest Paths one is given an undirected graph with edge costs and some pairs of vertices, and asks for an edge set of minimum cost whose deletion increases the distance of each pair by at least \(1\); that is, the set must meet every shortest path between the two vertices of each pair. Krause showed that the problem can be solved in polynomial time when all pairs have a vertex in common and that it is NP-hard for two disjoint pairs, and left open the remaining case of three pairs: the three pairs of three given vertices (Oberwolfach Report 50/2005; thesis, Braunschweig 2006). We show that this case is NP-hard, with edge costs and with unit costs. The proof is a short reduction from the minimum cut problem with three terminals: from a graph \(H\) with edge set \(D\) we build a bipartite graph with three terminals in which the minimum cost of a blocking set is \(2\,w(D)\) plus the minimum weight of a three-terminal cut of \(H\), for every positive integral weight \(w\) on \(D\). So the question of record OWR-1111-001 of the UnsolvedMath collection, to determine the complexity of the problem for three vertices, with or without edge costs, has the answer: NP-hard in both cases, and the decision problem is NP-complete. The construction was tested on all connected graphs \(H\) with at most six vertices. The hardness of the three-terminal cut problem is the theorem of Dahlhaus, Johnson, Papadimitriou, Seymour and Yannakakis. No proof or statement of the result was found in the literature accessible to us; a search that finds nothing is not a proof of novelty. This is an unrefereed note.