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.