For a given s–t planar directed network with lower and upper arc capacities we find those k arcs the removal of which minimizes the flow value of the maximum flow. Such arcs are called the k most vital arcs of the network. Analogously we find the k most vital nodes. Furthermore, we find the k bicriterial lexicographical most vital elements, the removal of which minimizes the maximum flow value first, and on the other hand, is the ‘cheapest’ variant. 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.
