How Vulnerable is an Undirected Planar Graph with Respect to Max Flow

We study the problem of computing the vitality of edges and vertices with respect to the st-max flow in undirected planar graphs, where the vitality of an edge/vertex is the st-max flow decrease when the edge/vertex is removed from the graph. This allows us to establish the vulnerability of the graph with respect to the st-max flow. We give efficient algorithms to compute an additive guaranteed approximation of the vitality of edges and vertices in planar undirected graphs. We show that in the general case high vitality values are well approximated in time close to the time currently required to compute st-max flow O(n log log n). We also give improved, and sometimes optimal, results in the case of integer capacities. All our algorithms work in O(n) space.