Preventing Small \(\mathbf {(s,t)}\)-Cuts by Protecting Edges

We introduce and study Weighted Min (s, t)-Cut Prevention, where we are given a graph \(G=(V,E)\) with vertices s and t and an edge cost function and the aim is to choose an edge set D of total cost at most d such that G has no (s, t)-edge cut of capacity at most a that is disjoint from D. We show that Weighted Min (s, t)-Cut Prevention is NP-hard even on subcubcic graphs when all edges have capacity and cost one and provide a comprehensive study of the parameterized complexity of the problem. We show, for example W[1]-hardness with respect to d and an FPT algorithm for a.