Blocking Small Cuts in a Network, and Related Problems
Daniel A. Bienstock, Nicole Romito Diaz · SIAM Journal on Computing · 1993
Let G be a graph with weights on the edges, S a subset of vertices, and k an integer. The problem of computing a minimum-weight subset of edges that meets all the cuts of cardinality $ \leqslant k$ that separate pairs of vertices in S is considered. This problem is motivated by issues in network survivability. Assuming $|S| = 2$, it is shown that although this problem is NP-hard, it can be solved in linear time for each fixed value of k. Furthermore, if $|S| > 2$, the problem is NP-hard even for small values of k but can be solved in linear time for each fixed k and $|S|$.