Max flow vitality in general and st-planar graphs

The vitality of an arc/node of a graph with respect to the maximum flow between two fixed nodes is defined as the reduction of the maximum flow caused by the removal of that arc/node. In this paper we address the issue of determining the vitality of arcs and/or nodes for the network flow problem over various classes of graphs and digraphs. First of all we show how to compute the vitality of all arcs in a general undirected graph by solving $n-1$ max flow instances, i.e., in worst case time $O(n \cdot \mbox{MF}(n,m))$, where $\mbox{MF}(n,m)$ is the time needed to solve a max-flow instance. In $st$-planar graphs (directed or undirected) we can compute the vitality of all arcs and all nodes in $O(n)$ worst case time. Moreover, after determining the vitality of arcs and/or nodes, and given a planar embedding of the graph, we can determine the vitality of a "contiguous" (w.r.t. that embedding) set of arcs/nodes in time proportional to the size of the set. In the case of general undirected planar graphs, the vitality of all nodes/arcs is computed in $O(n \log n)$ worst case time, while for the directed planar case we solve the same problem in $O(np)$, where $p$ is the number of arcs in a path from $s^{*}$ to $t^{*}$ in the dual graph.