Finding the \(k\) most vital elements of an s-t planar directed network (Q2723997)

The removal of \(k\) network elements (arcs or nodes) can reduce the value of maximum flow through any given s-t network. Those \(k\) elements which minimize the resulting flow value are called the \(k\) most vital elements of the network. Such problems arise if one wants to know in advance what the consequences will be if some of the network elements terminate their function or have to be switched off. In this paper, for an s-t planar directed network with lower and upper capacities, the author proposes an algorithm (of time complexity \(O(knm)\), \(n\) and \(m\) being the numbers of nodes and arcs, respectively) for finding the \(k\) most vital arcs. The algorithm is based on the duality concept for planar graphs. Also included is its modified version (of time complexity \(O(k^2nm)\)) which is superior with respect to memory requirements. To find the \(k\) most vital nodes, it is shown how one can reduce this problem to the former one by some well-known transformations (not affecting the time complexity of the resulting algorithms). Finally, the author describes a procedure for finding the \(k\) bicriterial lexicographically most vital elements (arc or/and nodes), the removal of which minimizes the maximum flow value first, and on the other hand, gives rise to the cheapest variant.