=Paper=
{{Paper
|id=Vol-3741/paper72
|storemode=property
|title=Max Flow Vulnerability of Undirected Planar Networks
|pdfUrl=https://ceur-ws.org/Vol-3741/paper72.pdf
|volume=Vol-3741
|authors=Lorenzo Balzotti,Paolo G. Franciosa
|dblpUrl=https://dblp.org/rec/conf/sebd/BalzottiF24
}}
==Max Flow Vulnerability of Undirected Planar Networks==
<pdf width="1500px">https://ceur-ws.org/Vol-3741/paper72.pdf</pdf>
<pre>
                                Max Flow Vulnerability of Undirected Planar
                                Networks
                                Lorenzo Balzotti1,* , Paolo G. Franciosa2
                                1
                                  Department of Computer, Control, and Management Engineering “Antonio Ruberti”, Sapienza University of Rome, Via
                                Ariosto 25, 00185, Rome, Italy.
                                2
                                  Department of Statistical Science, Sapienza University of Rome, p.le Aldo Moro 5, 00185 Rome, Italy.


                                           Abstract
                                           In the real world, planar networks commonly model utility distribution networks such as gas pipelines,
                                           water distribution, city’s electric grid, and transportation networks like railways and highways. Eval-
                                           uating the vulnerability of these networks is crucial on several point of view: in a military context in
                                           order to prevent terrorist attack, or for maintenance to prevent wear and tear or natural disasters from
                                           inflicting extremely severe damage. This work aims to evaluate the vulnerability of undirected planar
                                           network studying the decrease of maximum 𝑠𝑡-flow when an edge or a vertex is removed, that is, we
                                           propose algorithms for computing the max flow vitality of edges and vertices.
                                               Our algorithms are applied to real world scenarios, and we prove that high vitality values are well
                                           approximated in time close to the time currently required to compute 𝑠𝑡-max flow 𝑂(𝑛 log log 𝑛). All
                                           our algorithms work in 𝑂(𝑛) space.

                                           Keywords
                                           planar networks, undirected networks, max flow, vitality, vulnerability




                                1. Introduction
                                The design and construction of networks are important topics in today’s world. Establishing the
                                vulnerability of a network is crucial to prevent severe damage. There is no universal definition
                                of vulnerability, as the same network can be assessed using different metrics, resulting in it
                                being deemed vulnerable or robust depending on the metric used [2, 3].
                                   In this paper, we focus on undirected planar networks and study vulnerability with respect
                                to the maximum flow. It’s worth noting that planar networks find commonly application in
                                urban science for representing, either directly or with high accuracy, various infrastructure
                                networks [4], as water distribution networks [5, 6] and lots of streets patterns [7, 8]. The cities
                                structure are the subject of many studies [9, 10, 11, 12] based on their planar aspects; see [13, 14]
                                for a complete bibliography.
                                   We focus our study on the 𝑠𝑡-maximum flow vitality, that is the 𝑠𝑡-max flow decrease when
                                an edge or a vertex is removed, where 𝑠 and 𝑡 are two fixed vertices. A practical metric
                                for assessing the overall vulnerability of a network may involve considering the count of

                                SEBD 2024: 32nd Symposium on Advanced Database Systems, June 23-26, 2024, Villasimius, Sardinia, Italy
                                ⋆
                                  A preliminary version of this paper appeared in [1].
                                *
                                  Corresponding author.
                                $ lorenzo.balzotti@uniroma1.it (L. Balzotti); paolo.franciosa@uniroma1.it (P. G. Franciosa)
                                 0000-0001-6191-9801 (L. Balzotti); 0000-0002-5464-4069 (P. G. Franciosa)
                                         © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).




CEUR
                  ceur-ws.org
Workshop      ISSN 1613-0073
Proceedings
edges/vertices exhibiting high vitality, that is, elements whose deletion implies serious damage
to the 𝑠𝑡-maximum flow value. Thus, if all edges and vertices have low vitality, the network
can be deemed robust. We refer to [15, 16, 17] for surveys on several kind of robustness and
vulnerability problems discussed by an algorithmic point of view.
   In networks algorithms, the effect of edges removal/damage on the max flow value has been
studied since 1963, only a few years after the pioneering paper by Ford and Fulkerson [18] in
1956. Wollmer [19] presented an algorithm for determining the most vital edge in a railway
network, and other studies about max flow interdiction were carried out on the planar Russian
railway [20, 21] reported in Figure 1. According to Schrijver [22], in those year the study of
vitality and interdiction on maximum flow problem arose from the US Air Force’s desire to
disrupt the transportation capabilities of their adversaries.




Figure 1: An illustrative real-world instance of a planar maximum flow problem is depicted in the
schematic diagram of the railway network spanning the Western Soviet Union and Eastern European
countries, as presented by Harris and Ross [20].


   Ratliff and Sicilia [23] describe an algorithm for the 𝑘 most vital edges, where the removal of
these edge is simultaneous. Wood [24] showed that this problem is NP-hard in the strong sense,
while its approximability has been studied in [25, 26]. Other interdiction problems studied
in the literature include: shortest paths [27], minimum spanning tree [28, 29, 30], maximum
matching [31, 32] and connectivity [33].

Previous work A recent survey on exact 𝑠𝑡-max flow algorithms can be found in [34].
The best know algorithms for general graphs solve the problem in 𝑂(𝑚𝑛) time [35, 36]. For
undirected planar graphs a better result in 𝑂(𝑛 log log 𝑛) is presented by Italiano et al. [37],
while for planar directed graphs Borradaile and Klein [38] propose an 𝑂(𝑛 log 𝑛) time algorithm.
The easier 𝑠𝑡-planar case (that is when 𝑠 and 𝑡 are in the same face of a planar embedding) is
reduced by Hassin [39] to the computation of a single source shortest paths; that can be solved
in 𝑂(𝑛) time [40]. Finally, Eisenstat and Klein [41] illustrate how to compute the max flow in
undirected unweighted planar graphs in optimal 𝑂(𝑛) time.
   There are a few results focused on max flow vitality. In [42] the vitality of each edge and vertex
is computed in optimal 𝑂(𝑛) time in the 𝑠𝑡-planar case. The dynamic max flow algorithms
presented in [37, 43] allow also to computed edge and vertex vitality for undirected planar
graphs, we remind to Theorem 3 for a more in-depth discussion.

Our contribution We present fast algorithms for computing an additive guaranteed approxi-
mation of the 𝑠𝑡-max flow vitality for both edges and vertices with capacities below a chosen
threshold 𝐶. In Section 4 we explain how to use our results in real world scenarios.
   Let 𝐺 be an undirected planar graphs, let 𝐸(𝐺) and 𝑉 (𝐺) be its set of edges and vertices,
respectively, and let 𝑠 and 𝑡 be two fixed vertices. Let us denote by MF𝐺 or MF if no confusion
arises, its 𝑠𝑡-max flow. Let 𝑐 : 𝐸(𝐺) → R+ be the edge capacity function, we define the capacity
𝑐(𝑣) of a vertex 𝑣 as the sum of the capacities of all edges incident on 𝑣.
   Formally, the 𝑠𝑡-max flow vitality of a set 𝑆 ⊆ (𝑉 (𝐺) ∖ {𝑠, 𝑡}) ∪ 𝐸(𝐺), denoted by 𝑣𝑖𝑡(𝑆),
corresponds to MF𝐺 − MF𝐺−𝑆 , where 𝐺 − 𝑆 is the graph derived from 𝐺 by deleting set 𝑆. Our
main results are summarized in the following two theorems. We show that we can compute an
approximated value of both edge and vertex vitalities with an additive error lower than 𝛿 > 0,
where 𝛿 is an arbitrarily fixed vitality. All our algorithms work in 𝑂(𝑛) space.

Theorem 1. Let 𝐺 be a planar graph with positive edge capacities. Then for any 𝐶, 𝛿 > 0, we
can compute a value 𝑣𝑖𝑡𝛿 (𝑒) ∈ (𝑣𝑖𝑡(𝑒) − 𝛿, 𝑣𝑖𝑡(𝑒)] for each 𝑒 ∈ 𝐸(𝐺) satisfying 𝑐(𝑒) ≤ 𝐶, in
𝑂( 𝐶𝛿 𝑛 + 𝑛 log log 𝑛) time.

Theorem 2. Let 𝐺 be a planar graph with positive edge capacities. Then for any 𝐶, 𝛿 > 0, we
can compute a value 𝑣𝑖𝑡𝛿 (𝑣) ∈ (𝑣𝑖𝑡(𝑣) − 𝛿, 𝑣𝑖𝑡(𝑣)] for each 𝑣 ∈ 𝑉 (𝐺) satisfying 𝑐(𝑣) ≤ 𝐶, in
𝑂( 𝐶𝛿 𝑛 + 𝑛 log 𝑛) time.

  In the full version of the paper [1], results in the cases of integer and bounded capacities and
are presented. Those results are obtained thanks to better algorithm for computing distances in
these particular cases [44, 45]. In what follows, we focus only on edge vitality, and we refer to
the full version for results and approach regarding vertex vitality.

Outline Our procedure is split into two parts. We start from the approach introduced by Itai
and Shiloach’s [46] for computing the 𝑠𝑡-max flow in undirected planar graphs, see Section 2.
They translate the max flow computation into finding non-crossing shortest paths in graph 𝐷,
which is derived from the dual graph of 𝐺. We use this construction to prove that edge vitalities
can be inferred by knowing some distances in 𝐷, see Proposition 1. In the second part, which
is exposed in Section 3, we compute required distances by introducing a divide-and-conquer
strategy, which consists in slicing 𝐷 via non-crossing shortest paths, see Lemma 1.
   In Section 4 we apply our results to real world scenario, and in Section 5 conclusions and
open problems are presented.


2. From vitalities to distances
The first part of our approach is based on the work by Itai and Shiloach [46], that computes the
𝑠𝑡-maximum flow of 𝐺 via 𝑠𝑡-separating cycle in its dual graph 𝐺* . They build an auxiliary
graph 𝐷𝐺 (if no confusion arises, denoted as 𝐷) where the 𝑠𝑡-separating cycles correspond to
non-crossing shortest paths between pairs vertices on the external face of 𝐷. Starting from
𝐷, we explain how computing edge vitalities of 𝐺 by finding some distances in 𝐷, this is our
main result of this section and it is exposed in Proposition 1. Now we describe into details the
construction of 𝐷 by Itai and Shiloach [46].
    We observe that every vertex in 𝐺* corresponds to a face in 𝐺. In Figure 2 on the left, there
is graph 𝐺 in black continuous edges, and graph 𝐺* in red dashed edges. In [46], the authors
first fix a shortest path 𝜋 from 𝑣𝑠* to 𝑣𝑡* , where 𝑣𝑠* to 𝑣𝑡* are the vertices in 𝐺* corresponding
to faces in 𝐺 containing 𝑠 and 𝑡, respectively. Without loss of generality, we assume that
𝜋 = {𝑣1* , 𝑣2* , . . . , 𝑣𝑘* }, with 𝑣1* = 𝑣𝑠* and 𝑣𝑘* = 𝑣𝑡* . Path 𝜋 is represented in green in Figure 2
on the left. Then they “cut” 𝐺* along 𝜋 obtaining graph 𝐷𝐺 (for convenience we refer to it as
graph 𝐷) represented in Figure 2 on the right.
    They double path 𝜋 into the paths 𝜋𝑥 and 𝜋𝑦 , the first has vertices {𝑥1 , . . . , 𝑥𝑘 } and the latter
{𝑦1 , . . . , 𝑦𝑘 }. In order to split the graph 𝐺* into two, 𝜋 has to split the whole plane into two
parts. To obtain this, they add two dummy vertices 𝛼 and 𝛽, and they connect them to 𝑣𝑠* and
𝑣𝑡* , respectively. If 𝛼 is inside the face containing 𝑠 and 𝛽 inside the face containing 𝑡, then
the edges 𝛼𝑣𝑠* and 𝛽𝑣𝑡* can be extended to the infinity, splitting the whole plane where 𝐺* is
embedded into two arbitrarily parts 𝐴 and 𝐵; without loss of generality we say that 𝐴 is the
part “above” 𝜋 and 𝐵 the part “below” 𝜋. Now we can explain how to build graph 𝐷.
    For any 𝑖 ∈ [𝑘], where [𝑘] = {1, . . . , 𝑘}, edges in 𝐺* incident on each 𝑣𝑖* from below 𝜋 are
moved to 𝑦𝑖 and edges incident on 𝑣𝑖* from above 𝜋 are moved to 𝑥𝑖 . For each 𝑒* ∈ 𝜋 in 𝐺* , in
𝐷 the copy of 𝑒* in 𝜋𝑥 is denoted by 𝑒*𝑥 , and the copy of 𝑒* in 𝜋𝑦 is denoted by 𝑒*𝑦 . Note that
every vertex 𝑣 in 𝐺 generates a face 𝑓𝑣* in 𝐺* , that still remains a face in 𝐷, still denoted by
𝑓𝑣* . If 𝑒* in 𝐺* does not belong to 𝜋, then we still denote the corresponding edge in 𝐷 by 𝑒* .
Similarly, if 𝑉𝑖* in 𝐺* does not belong to 𝜋, then we still denote the corresponding vertex in 𝐷
by 𝑣𝑖* (this happens when 𝑖 > 𝑘).
                                 *
                                𝑣∞
                                                                              𝑦1                𝑦2           𝑦3              𝑦4
       𝑎                    𝑏               𝑐                     𝑑
                𝑣1*                                                                  𝑓𝑒*
                                    𝑣2*                   𝑣5*
                            𝜋             𝑣4*                                              𝑣7*                   𝑣6*
            𝛼                       𝑔                                                𝑓ℎ*
                      𝑒                                                                              𝑓𝑖*
                                           𝛽                                  𝑣8*                           𝑓𝑑*
                                    𝑣3*                         𝑣6*                                                    𝑣5*
                                                                                                  *
                                                𝑡                                                𝑣∞        𝑓𝑐*
                      𝑣8*                           𝑣7*                             𝑓𝑎*
            𝑠                                                         𝑖                   𝑓𝑏*                 𝑓𝑔*
                                ℎ                                             𝑥1                𝑥2           𝑥3              𝑥4
Figure 2: on the left graph 𝐺 in black continuous line, 𝐺 in red dashed lines, shortest path 𝜋 from 𝑣𝑠*
                                                                          *

(𝑣1* ) to 𝑣𝑡* (𝑣𝑘* ) in green, 𝛼 and 𝛽 are dummy vertices. On the right graph 𝐷.


  For 𝑖 ∈ [𝑘], we define 𝑑𝑖 = dist𝐷 (𝑥𝑖 , 𝑦𝑖 ). Itai and Shiloach [46] proved that MF = min𝑖∈[𝑘] 𝑑𝑖 ,
that is, the 𝑠𝑡-maximum flow is equal to the minimum 𝑠𝑡-separating cycle. We observe that
the removal of an edge 𝑒 in 𝐺 corresponds to contracting vertices of 𝑒* in 𝐺* into one, and
so some 𝑑𝑖 ’s may be shorten. For this reason, for 𝑒* ∈ 𝑉 (𝐷) and 𝑖 ∈ [𝑘] we define 𝑑𝑖 (𝑒* ) =
min{𝑑𝑖 , dist𝐷 (𝑥𝑖 , 𝑒* ) + dist𝐷 (𝑦𝑖 , 𝑒* )}. Note that 𝑑𝑖 (𝑒* ) represents the distance in 𝐷 from 𝑥𝑖 to
𝑦𝑖 if all vertices of 𝑒* are contracted into one. For 𝑒 ∈ 𝐸(𝐺) we define MF𝑒 as the 𝑠𝑡-maximum
flow in graph 𝐺 − 𝑒. It follows that 𝑣𝑖𝑡(𝑒) = MF − MF𝑒 and, trivially, 𝑣𝑖𝑡(𝑒) > 0 if and only if
MF𝑒 < MF. In the following proposition we translate the problem of computing edge vitality in
𝐺 into computing distances in 𝐷.
                                          *           *                            *        *
                          {︀ 𝑒 of 𝐺, if* 𝑒 ̸∈ 𝜋* in}︀𝐺 , then MF𝑒 = min𝑖∈[𝑘] {𝑑𝑖 (𝑒 )}. If 𝑒 ∈ 𝜋
Proposition 1. For every edge
    *
in 𝐺 , then MF𝑒 = min𝑖∈[𝑘] min{𝑑𝑖 (𝑒𝑥 ), 𝑑𝑖 (𝑒𝑦 )} .


3. Divide-and-conquer strategy
In this section we explain our divide-and-conquer strategy that leads to Lemma 1, which is the
key to derive Theorem 1. We slice graph 𝐷 along shortest non-crossing 𝑥𝑖 𝑦𝑖 ’s paths.
   From now on, for 𝑖 ∈ [𝑘] we fix a shortest 𝑥𝑖 𝑦𝑖 path 𝑝𝑖 , and we consider that {𝑝𝑖 }𝑖∈[𝑘] is a set
of pairwise single-touch non-crossing shortest paths, where two paths are single-touch if their
intersection is still a path. All the 𝑝𝑖 ’s can be computed in 𝑂(𝑛 log log 𝑛) time by the algorithm
in [37], and ⋃︀
              their lengths in 𝑂(𝑛) time by the algorithm in [44].
   Let 𝑈 = 𝑖∈[𝑘] 𝑝𝑖 , see Figure 3(a). The single-touch property assures us that 𝑈 is a forest.
Given an 𝑎𝑏 path 𝑝 and a 𝑏𝑐 path 𝑞, we define 𝑝 ∘ 𝑞 as the (possibly not simple) 𝑎𝑐 path obtained
by the union of 𝑝 and 𝑞. Each 𝑝𝑖 ’s splits 𝐷 into two parts as shown in the following definition
and in Figure 3(b).

Definition 1. For every 𝑖 ∈ [𝑘], we define Left𝑖 as the subgraph of 𝐷 bounded by the cycle
𝜋𝑦 [𝑦1 , 𝑦𝑖 ] ∘ 𝑝𝑖 ∘ 𝜋𝑥 [𝑥𝑖 , 𝑥1 ] ∘ 𝑙, where 𝑙 is the leftmost 𝑥1 𝑦1 path in 𝐷. Similarly, we define Right𝑖
as the subgraph of 𝐷 bounded by the cycle 𝜋𝑦 [𝑦𝑖 , 𝑦𝑘 ] ∘ 𝑟 ∘ 𝜋𝑥 [𝑥𝑘 , 𝑥𝑖 ] ∘ 𝑝𝑖 , where 𝑟 is the rightmost
𝑥𝑘 𝑦𝑘 path in 𝐷.

𝑦1 𝑦2 𝑦 𝑦 𝑦 𝑦6             𝑦7    𝑦8 𝑦1                               𝑦𝑘 𝑦1                       𝑦𝑗      𝑦𝑘
       3 4 5                                        𝑦𝑖                            𝑦𝑖


                                          Left𝑖            Right𝑖                       Ω𝑖,𝑗


𝑥1 𝑥2 𝑥 𝑥 𝑥5 𝑥6            𝑥7    𝑥8 𝑥1                               𝑥𝑘 𝑥1                       𝑥𝑗      𝑥𝑘
       3 4                                          𝑥𝑖                            𝑥𝑖
           (a)                                      (b)                                 (c)
Figure 3: in (a) the graph 𝑈 in bold and in (b) subgraphs Left𝑖 and Right𝑖 are highlighted. In (c) subgraph
Ω𝑖,𝑗 , for some 𝑖 < 𝑗.


   Based on Definition 1, for every 𝑖, 𝑗 ∈ [𝑘], with 𝑖 < 𝑗, we define Ω𝑖,𝑗 = Right𝑖 ∩ Left𝑗 , see
Figure 3(c). Our divide-and-conquer strategy is based on these slices Ω𝑖,𝑗 . Now we have to
bucket the indices {1, 2, . . . , 𝑘} so that these slices have some special distance properties.
   For every 𝑟 ∈ N, we define 𝐿𝑟 = (ℓ𝑟1 , . . . , ℓ𝑟𝑧𝑟 ) as the ordered list of indices in [𝑘] such that
𝑑𝑗 ∈ [MF + 𝛿𝑟, MF + 𝛿(𝑟 + 1)), for all 𝑗 ∈ 𝐿𝑟 , and ℓ𝑟𝑗 < ℓ𝑟𝑗+1 for all 𝑗 ∈ [𝑧𝑟 − 1]. If no confusion
arises, we omit the superscript 𝑟; thus we write ℓ𝑖 in place of ℓ𝑟𝑖 .
  Now we can formulate properly our slicing strategy in the following lemma. Indeed, we
note that every edge in 𝐷 is always contained in a slice. The following lemma is the key of
our slicing strategy. In particular, Lemma 1 can be applied for computing distances required in
Proposition 1.

Lemma 1. Let 𝑟 > 0 and let 𝐿𝑟 = (ℓ1 , ℓ2 , . . . , ℓ𝑧 ). Let 𝑒* be a vertex in 𝐷 and let 𝑖 ∈ [𝑧 − 1]
satisfy 𝑒* ⊆ Ωℓ𝑖 ,ℓ𝑖+1 . Then
                            min 𝑑ℓ (𝑒* ) > min{𝑑ℓ𝑖 (𝑒* ), 𝑑ℓ𝑖+1 (𝑒* )} − 𝛿.
                            ℓ∈𝐿𝑟

Moreover, if 𝑒* ⊆ Leftℓ1 (resp., 𝑒* ⊆ Rightℓ𝑧 ) then minℓ∈𝐿𝑟 𝑑ℓ (𝑒* ) > 𝑑ℓ1 (𝑒* ) − 𝛿 (resp.,
minℓ∈𝐿𝑟 𝑑ℓ (𝑒* ) > 𝑑ℓ𝑧 (𝑒* ) − 𝛿).

  An application of Lemma 1 is in Figure 4. By Proposition 1, we need 𝑑𝑖 (𝑒* ) for all 𝑖 ∈ [𝑘]
and consider the minimum value. This can be obtained by 2𝑘 SSSP instances in 𝐷 (one with
source 𝑥𝑖 and one with source 𝑦𝑖 for every 𝑖 ∈ [𝑘]). But we can compute minℓ∈𝐿𝑟 𝑑ℓ (𝑒* )
with only 4 SSSP instances focused on the slice of the graph 𝐷 containing 𝑒* ; in a way, we
obtain the minimum among more indices by paying the additive error 𝛿. In Figure 4, it holds
minℓ∈𝐿𝑟 𝑑ℓ (𝑒* ) ≥ min{𝑑ℓ3 (𝑒* ), 𝑑ℓ4 (𝑒* )} − 𝛿.
                                    𝑦 ℓ1               𝑦ℓ3 𝑦ℓ4        𝑦ℓ𝑧−1 𝑦ℓ𝑧
                                             𝑦 ℓ2
                                               Ωℓ2 ,ℓ3
                                   Ωℓ1 ,ℓ2
                                                    Ωℓ3 ,ℓ4           Ωℓ𝑧−1 ,ℓ𝑧
                                                                  *
                                                              𝑒
                                               Ωℓ2 ,ℓ3
                                    𝑥 ℓ1                  𝑥ℓ𝑧−1 𝑥ℓ𝑧
                                                𝑥 ℓ3 𝑥 ℓ4
                                             𝑥 ℓ2
Figure 4: by Lemma 1, it holds that minℓ∈𝐿𝑟 𝑑ℓ (𝑒* ) ≥ min{𝑑ℓ3 (𝑒* ), 𝑑ℓ4 (𝑒* )} − 𝛿.


 In the full version of this work [1] it is proved how to easily derive Theorem 1 from Lemma 1,
moreover, the discussion is extended to vertex vitality, see Theorem 2.


4. Practical utilization in real world scenario
In this section we explain how to use the results stated in Theorem 1 and Theorem 2 to real world
scenario. In particular we describe how to determine 𝐶 and 𝛿 according to the distribution of
edge capacities. Note that in real world applications one is usually interested in determining edge
and/or vertices with high vitality, that is, edge or vertices whose deletion implies serious damage
to the 𝑠𝑡-maximum flow value. This is strictly linked to evaluating the robustness/vulnerability
of the network. Before arguing with our theorems, we report here the best algorithm for
computing edge vitalities stated in [37, 43].

Theorem 3 ([37, 43]). Let 𝐺 be a planar graph with positive edge capacities. Then it is possible to
                                                                                      ℎ𝑛
compute the vitality of ℎ single edges or the vitality of a set of ℎ edges in 𝑂(min{ log 𝑛 +𝑛 log log 𝑛,
ℎ𝑛2/3 log8/3 𝑛 + 𝑛 log 𝑛}) time.
  We underline that the previous algorithm can compute the exact vitality of ℎ edges, but in
order to obtain information about all edges, we need to apply it with ℎ = 𝑛.
  Returning to the discussion of our theorems, we observe that the capacities may be not
bounded by any function of 𝑛. Despite this, we now introduce some procedures to make 𝐶/𝛿
constant. In this way, the time complexity of Theorem 1 becomes 𝑂(𝑛 log log 𝑛), that is the
best current time bound for computing the 𝑠𝑡-max flow [37]. Let’s start with the following
crucial remark, where 𝑐𝑚𝑎𝑥 = max𝑒∈𝐸(𝐺) 𝑐(𝑒).

Remark 1. [Bounding capacities]. We can bound all edge capacities higher than MF to MF,
obtaining a new bounded edge capacity function. This change has no impact on the 𝑠𝑡-max flow
value or the vitality of any edge/vertex. Thus w.l.o.g., we can assume that 𝑐𝑚𝑎𝑥 ≤ MF.

   After Remark 1, from now on we assume that 𝑐𝑚𝑎𝑥 ≤ MF. We apply the result in Theorem 1
to two real world scenarios. In the first scenario we assume that the distribution of capacities is
general, i.e., there is no function that relates a capacity value to the number of edges having that
capacity value. In the second scenario we study what happens when the distribution of edge
capacities can be described by a power-law; but actually, this can be applied in every case there
are few edges (outlier) with high capacity. Take into account that the power-law distribution is
very common in real world planar networks, especially in distribution networks.
   In Figure 5 we outline the following discussion. The figure shows how to determine constants
𝐶 and 𝛿 in two different scenarios (the edge capacities are synthetic).




                       (a)                                                (b)

Figure 5: how to determine optimal 𝐶 and 𝛿 according to the distribution of edge capacities.


∙ General distribution. In this case we can set 𝐶 = 𝑐𝑚𝑎𝑥 and 𝛿 = 𝐶/𝑘, for some small constant
𝑘, e.g., 𝑘 = 10, 50, 100. So we have a good approximation of edges with high vitality. Indeed,
if an edge has vitality comparable with MF, then we obtain its vitality with an additive error
smaller than MF/𝑘 (because of Remark 1). On the other hand, we have a bad approximation for
edges with low capacity; in Figure 5(a) they correspond to edges on the left of the green line.
This is not a problem because “small capacity” corresponds to “small vitality”, indeed the vitality
of an edge is at most its capacity. With this settings the time complexity stated in Theorem 1
becomes 𝑂(𝑛 log log 𝑛), that is the time currently required for the computation of the 𝑠𝑡-max
flow.
∙ Power-law distribution. We cannot apply the same reasoning to the previous case, in fact if we
choose 𝐶 = 𝑐𝑚𝑎𝑥 and 𝛿 = 𝐶/𝑘 for small constant 𝑘, then we obtain a bad approximation of all
edges on the left of the red line in Figure 5(b). They are absolutely the majority of edges. So we
set 𝐶 = 𝑐𝑚𝑎𝑥 /𝑘 and 𝛿 = 𝐶/ℓ, for some constant ℓ, and we compute the (exact) vitality of edges
whose capacity is greater than 𝐶 via Theorem 3. Note that this set of edges is small because
of the power law distribution of capacities. The vitality of edges computed by our algorithm
has an additive error smaller than MF 𝑘ℓ , because of Remark 1; it may be an acceptable error even
for small values of 𝑘 and ℓ. Also in this case, the overall time complexity is equal or close to
𝑂(𝑛 log log 𝑛).

   Since our algorithms provide approximate vitalities with an additive error, it is possible
having as output 𝑣𝑖𝑡𝛿 (𝑒) = 0 for each 𝑒 ∈ 𝐸(𝐺). At first sight, it may appear as an useless
result, but actually we verify the robustness of the network because all edges have vitality
smaller than 𝛿. The same reasoning can be applied also to vertex vitality, and consequently to
Theorem 2 by observing that in a real-world planar network there are usually a few vertices with
high degree (as also implied by Euler’s formula). We conclude by a fast comparison among our
results and the algorithm stated in Theorem 3. It’s clear that we compute approximated vitalities
while Theorem 3 allows to compute exact vitality, but if one is interested in understanding the
robustness/vulnerability of the network, then it is necessary to evaluate the vitality (exact or
approximated) of all edges and/or all vertices. Our algorithms obtain this in a time equal o
close to 𝑂(𝑛 log log 𝑛), while we need 𝑂(𝑛5/3 log8/2 𝑛) time by using the result in Theorem 3.
Hence our results provide considerably faster algorithms.


5. Conclusions and open problems
We describe fast algorithms for computing an additive guaranteed approximation of the 𝑠𝑡-max
flow vitality of both edges and vertices in undirected planar networks. The vulnerability of
real world planar networks can be established via our algorithms under various edge capacity
distributions.
   We left open the problem of computing the exact vitality of all edges and vertices in the same
time required for computing the max flow value, as is already known for the 𝑠𝑡-planar case.


References
 [1] L. Balzotti, P. G. Franciosa, How vulnerable is an undirected planar graph with respect
     to max flow, Networks 83 (2024) 570–586. doi:https://doi.org/10.1002/net.22205.
 [2] S. Freitas, D. Yang, S. Kumar, H. Tong, D. H. Chau, Graph vulnerability and robustness:
     A survey, IEEE Transactions on Knowledge and Data Engineering 35 (2023) 5915–5934.
     doi:10.1109/TKDE.2022.3163672.
 [3] H. V. Nath, Vulnerability assessment methods – a review, in: D. C. Wyld, M. Wozniak,
     N. Chaki, N. Meghanathan, D. Nagamalai (Eds.), Advances in Network Security and
     Applications, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, pp. 1–10. doi:10.1007/
     978-3-642-22540-6_1.
 [4] M. Barthélemy, Spatial networks, Physics Reports 499 (2011) 1–101. doi:https://doi.
     org/10.1016/j.physrep.2010.11.002.
 [5] V. Chauhan, Planar Graph Generation with Application to Water Distribution Networks,
     Ph.D. thesis, Clemson University, 2018.
 [6] M. Herrera, E. Abraham, I. Stoianov, A Graph-Theoretic Framework for Assessing the
     Resilience of Sectorised Water Distribution Networks, Water Resources Management 30
     (2016) 1685–1699. doi:10.1007/s11269-016-1245-6.
 [7] S. Marshall, Streets and Patterns, Routledge, 2004. doi:10.4324/9780203589397.
 [8] M. Southworth, E. Ben-Joseph, Streets and the Shaping of Towns and Cities, Island Press,
     2013.
 [9] M. Barthélemy, A. Flammini, Modeling Urban Street Patterns, Phys. Rev. Lett. 100 (2008)
     138702. doi:10.1103/PhysRevLett.100.138702.
[10] J. Buhl, J. Gautrais, N. Reeves, R. V. Solé, S. Valverde, P. Kuntz, G. Theraulaz, Topological
     patterns in street networks of self-organized urban settlements, The European Physical
     Journal B-Condensed Matter and Complex Systems 49 (2006) 513–522. doi:10.1140/
     epjb/e2006-00085-1.
[11] A. Cardillo, S. Scellato, V. Latora, S. Porta, Structural properties of planar graphs of urban
     street patterns, Phys. Rev. E 73 (2006) 066107. doi:10.1103/PhysRevE.73.066107.
[12] A. P. Masucci, D. Smith, A. Crooks, M. Batty, Random planar graphs and the London
     street network, The European Physical Journal B 71 (2009) 259–271. doi:10.1140/epjb/
     e2009-00290-4.
[13] G. Boeing, A multi-scale analysis of 27,000 urban street networks: Every us city, town,
     urbanized area, and zillow neighborhood, Environment and Planning B: Urban Analytics
     and City Science 47 (2020) 590–608. doi:10.1177/2399808318784595.
[14] M. P. Viana, E. Strano, P. Bordin, M. Barthelemy, The simplicity of planar networks,
     Scientific reports 3 (2013) 3495. doi:10.1038/srep03495.
[15] D. L. Alderson, G. G. Brown, W. M. Carlyle, L. A. Cox Jr, Sometimes There Is No “Most-Vital”
     Arc: Assessing and Improving the Operational Resilience of Systems, Military Operations
     Research 18 (2013) 21–37.
[16] L.-G. Mattsson, E. Jenelius, Vulnerability and resilience of transport systems – a discussion
     of recent research, Transportation Research Part A: Policy and Practice 81 (2015) 16–34.
     doi:https://doi.org/10.1016/j.tra.2015.06.002, resilience of Networks.
[17] A. T. Murray, An overview of network vulnerability modeling approaches, GeoJournal 78
     (2013) 209–221. doi:http://dx.doi.org/10.1007/s10708-011-9412-z.
[18] L. R. Ford, D. R. Fulkerson, Maximal Flow Through a Network, Canadian journal of Math-
     ematics 8 (1956) 399–404. doi:http://dx.doi.org/10.1007/978-0-8176-4842-8_
     15.
[19] R. D. Wollmer, Some Methods for Determining the Most Vital Link in a Railway Network,
     Rand Corporation, 1963.
[20] T. Harris, F. Ross, Fundamentals of a Method for Evaluating Rail Net Capacities, Technical
     Report, Rand Corporation, 1955.
[21] A. W. McMasters, T. M. Mustin, Optimal Interdiction of a Supply Network, Naval
     Research Logistics Quarterly 17 (1970) 261–268. doi:http://dx.doi.org/10.1002/
     nav.3800170302.
[22] A. Schrijver, On the history of the transportation and maximum flow problems,
     Mathematical programming 91 (2002) 437–445. doi:http://dx.doi.org/10.1007/
     s101070100259.
[23] H. D. Ratliff, G. T. Sicilia, S. Lubore, Finding the n Most Vital Links in Flow Networks,
     Management Science 21 (1975) 531–539. doi:http://dx.doi.org/10.1287/mnsc.21.
     5.531.
[24] R. K. Wood, Deterministic Network Interdiction, Mathematical and Computer Modelling
     17 (1993) 1–18. doi:http://dx.doi.org/10.1016/0895-7177(93)90236-R.
[25] D. S. Altner, Ö. Ergun, N. A. Uhan, The Maximum Flow Network Interdiction Problem:
     Valid Inequalities, Integrality Gaps, and Approximability, Operations Research Letters 38
     (2010) 33–38. doi:10.1016/j.orl.2009.09.013.
[26] C. A. Phillips, The Network Inhibition Problem, in: Proceedings of the Twenty-Fifth
     Annual ACM Symposium on Theory of Computing, ACM, 1993, pp. 776–785. doi:10.
     1145/167088.167286.
[27] E. Israeli, R. K. Wood, Shortest-path network interdiction, Networks 40 (2002) 97–111.
     doi:https://doi.org/10.1002/net.10039.
[28] L.-H. Hsu, R.-H. Jan, Y.-C. Lee, C.-N. Hung, M.-S. Chern, Finding the most vital edge with
     respect to minimum spanning tree in weighted graphs, Information Processing Letters 39
     (1991) 277–281. doi:https://doi.org/10.1016/0020-0190(91)90028-G.
[29] L.-H. Hsu, P.-F. Wang, C.-T. Wu, Parallel algorithms for finding the most vital edge with
     respect to minimum spanning tree, Parallel Computing 18 (1992) 1143–1155. doi:https:
     //doi.org/10.1016/0167-8191(92)90061-B.
[30] S. Banerjee, S. Saxena, Parallel algorithm for finding the most vital edge in weighted
     graphs, Journal of Parallel and Distributed Computing 46 (1997) 101–104. doi:https:
     //doi.org/10.1006/jpdc.1997.1383.
[31] R. Zenklusen, Matching interdiction, Discrete Applied Mathematics 158 (2010) 1676–1690.
     doi:https://doi.org/10.1016/j.dam.2010.06.006.
[32] M. Dinitz, A. Gupta, Packing interdiction and partial covering problems, in: M. Goemans,
     J. Correa (Eds.), Integer Programming and Combinatorial Optimization, Springer Berlin
     Heidelberg, Berlin, Heidelberg, 2013, pp. 157–168. doi:http://dx.doi.org/10.1007/
     978-3-642-36694-9_14.
[33] R. Zenklusen, Connectivity interdiction, Operations Research Letters 42 (2014) 450–454.
     doi:https://doi.org/10.1016/j.orl.2014.07.010.
[34] O. Cruz-Mejía, A. N. Letchford, A survey on exact algorithms for the maximum flow
     and minimum-cost flow problems, Networks 82 (2023) 167–176. doi:https://doi.org/
     10.1002/net.22169.
[35] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows (1988).
[36] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, M. Reddy, Applications of Network Optimization,
     Handbooks in Operations Research and Management Science 7 (1995) 1–83.
[37] G. F. Italiano, Y. Nussbaum, P. Sankowski, C. Wulff-Nilsen, Improved Algorithms for
     Min Cut and Max Flow in Undirected Planar Graphs, in: Proceedings of the 43rd ACM
     Symposium on Theory of Computing, ACM, 2011, pp. 313–322. doi:10.1145/1993636.
     1993679.
[38] G. Borradaile, P. N. Klein, An 𝑂(𝑛 log 𝑛) Algorithm for Maximum st-Flow in a Directed
     Planar Graph, Journal of the ACM 56 (2009) 9:1–9:30. doi:10.1145/1502793.1502798.
[39] R. Hassin, Maximum Flow in (s,t) Planar Networks, Information Processing Letters 13
     (1981) 107. doi:10.1016/0020-0190(81)90120-4.
[40] M. R. Henzinger, P. N. Klein, S. Rao, S. Subramanian, Faster Shortest-Path Algorithms for
     Planar Graphs, Journal of Computer and System Sciences 55 (1997) 3–23. doi:10.1006/
     jcss.1997.1493.
[41] D. Eisenstat, P. N. Klein, Linear-Time Algorithms for Max Flow and Multiple-Source
     Shortest Paths in Unit-Weight Planar Graphs, in: Symposium on Theory of Computing
     Conference, STOC’13, ACM, 2013, pp. 735–744. doi:10.1145/2488608.2488702.
[42] G. Ausiello, P. G. Franciosa, I. Lari, A. Ribichini, Max flow vitality in general and st-planar
     graphs, Networks 74 (2019) 70–78. doi:10.1002/net.21878.
[43] J. Łącki, P. Sankowski, Min-Cuts and Shortest Cycles in Planar Graphs in 𝑂(𝑛 log log 𝑛)
     Time, in: Algorithms - ESA 2011 - 19th Annual European Symposium, Proceedings,
     volume 6942 of Lecture Notes in Computer Science, Springer, 2011, pp. 155–166. doi:10.
     1007/978-3-642-23719-5\_14.
[44] L. Balzotti, P. G. Franciosa, Non-Crossing Shortest Paths in Undirected Unweighted Planar
     Graphs in Linear Time, Journal of Graph Algorithms and Applications 26 (2022) 589–606.
     doi:10.7155/jgaa.00610.
[45] L. Kowalik, M. Kurowski, Short Path Queries in Planar Graphs in Constant Time, in:
     Proceedings of the 35th Annual ACM Symposium on Theory of Computing, ACM, 2003,
     pp. 143–148. doi:10.1145/780542.780565.
[46] A. Itai, Y. Shiloach, Maximum Flow in Planar Networks, SIAM Journal on Computing 8
     (1979) 135–150. doi:10.1137/0208012.

</pre>