On the non-submodularity of the problem of adding links to minimize the effective graph resistance Massimo A. Achterberg*, Robert E. Kooij* Abstract We consider the optimisation problem of adding k k links to a given network, such that the resulting effective graph resistance is as small as possible. The problem was recently proven to be NP-hard, such that optimal solutions obtained with brute-force methods require exponentially many computation steps and thus are infeasible for any graph of realistic size. Therefore, it is common in such cases to use a simple greedy algorithm to obtain an approximation of the optimal solution. It is known that if the considered problem is submodular, the quality of the greedy solution can be guaranteed. However, it is known that the optimisation problem we are facing, is not submodular. For such cases one can use the notion of generalized submodularity, which is captured by the submodularity ratio γ \gamma . A performance bound, which is a function of γ \gamma , also exists in case of generalized submodularity. In this paper we give an example of a family of graphs where the submodularity ratio approaches zero, implying that the solution quality of the greedy algorithm cannot be guaranteed. Furthermore, we show that the greedy algorithm does not always yield the optimal solution and demonstrate that even for a small graph with 10 nodes, the ratio between the optimal and the greedy solution can be as small as 0.878. Keywords : Effective graph resistance, Network augmentation, Generalised submodularity, Greedy algorithms, Submodularity ratio 1 Introduction Many network metrics have been utilised to quantify the robustness of a network, see for instance [ 27 , 29 , 13 , 31 , 3 ] . Freitas et al . [ 14 ] classify robustness metrics into three types: metrics based on structural properties, such as edge connectivity or diameter; metrics based on the spectrum of the adjacency matrix, such as the spectral radius or spectral gap; and metrics based on the spectrum of the Laplacian matrix, for instance the algebraic connectivity and the effective graph resistance. The robustness is considered optimal for a complete network and minimal for disconnected networks. In this paper we consider the k -Graph Robustness Improvement Problem ( k -GRIP) [ 28 ] , in which one has to decide where k links are to be added to a given network G , such that the robustness is optimised. The set of placeable positions is not necessarily all currently non-existing links – there may be additional constraints. We call the set of placeable links V and denote the robustness measure by f . From here onward, we assume that the set of placeable links V equals all non-existing links, unless otherwise specified. For many choices of the robustness metric f , k -GRIP is known to be NP-hard. To overcome the difficulty of finding the optimal solution (often only possible using a brute-force algorithm), we apply a simple greedy algorithm. Out of all placeable links V , at each step the greedy algorithm selects a single link to add. This procedure is repeated until k links are added. The greedy algorithm often performs well in practice, but the solution quality in general cannot be guaranteed. The notion of submodularity was introduced by Nemhauser et al . [ 24 ] as a tool to guarantee the performance of the greedy algorithm. Submodularity implies that adding one element to a large set has relatively small influence, whereas it has a stronger influence on a small set. Nemhauser et al . [ 24 ] proved that if the robustness metric satisfies the submodularity condition, the corresponding optimisation problem can be solved with a polynomial-time greedy algorithm, whose performance is at least a factor \left(1-\frac{1}{e}\right) -close to the optimal solution, and moreover, there does not exist any better algorithm with the same complexity. A recent overview of submodularity is provided by [ 5 ] . The concept of submodularity was generalised by Das and Kempe [ 10 ] by introducing the submodularity ratio \gamma and was further generalised with the concept of curvature \alpha in [ 33 , 2 ] and for nonmonotone metrics [ 30 ] . In this paper we consider the effective graph resistance [ 11 ] as the robustness metric. The effective graph resistance not only covers the shortest path between any pair of nodes, but incorporates all paths between any two nodes. It has been shown in [ 34 ] that the problem of minimizing the effective graph resistance upon the addition of k links is non-submodular. In this paper we give an example of a family of graphs where the submodularity ratio approaches zero, implying that, even by using the concept of generalized submodularity, the solution quality of the greedy algorithm cannot be guaranteed. The remainder of the paper is as follows. We first show related work in Section 2 . Section 3 formally introduces the k -GRIP optimisation problem. We proceed by providing a counterexample for generalised submodularity in Section 4 for k -GRIP with the effective graph resistance. We compare the greedy algorithm with the brute-force method for many small graphs in Section 5 and show that the greedy algorithm does not always provide the optimal solution. Finally, we conclude in Section 6 . 2 Related work Several researchers investigated k -GRIP for specific robustness metrics. For instance, [ 38 ] considered 1 -GRIP, with as robustness metric the algebraic connectivity, i.e. the second-smallest eigenvalue of the Laplacian matrix L . They suggest several strategies, based upon topological and spectral properties of the graph, to decide which single link to add to the network, in order to increase the algebraic connectivity as much as possible. The algebraic connectivity for k -GRIP was considered by [ 16 , Chapter 8] . Under some light conditions, lower bounds for the quality of the greedy solution were obtained. It might be argued that the algebraic connectivity is not a proper robustness metric, because there are examples where adding a link to a graph, does not change the algebraic connectivity, see [ 17 ] . The NP-hardness of k -GRIP for the algebraic connectivity was proved in [ 23 ] . A nice overview of k -GRIP for the algebraic connectivity is presented in [ 20 ] , see the references [5–16] therein. Shan et al . [ 32 ] considered the node resistance as robustness metric, which is the sum of the effective resistances from one source node v to all other nodes. They assume V is the set of non-existing links from the source node v ; not all possible non-existing links. In that case, the node resistance is shown to be submodular. Papagelis [ 25 ] shows that k -GRIP with the average shortest path length as a robustness metric does not satisfy the submodularity constraint, but accurate greedy solutions can be obtained. Van Mieghem et al . [ 37 ] consider a link removal problem with the spectral radius (largest eigenvalue of the adjacency matrix) as a robustness metric and prove this problem is NP-hard. Baras and Hovareshti [ 1 ] consider the problem of adding k links to a given network, such that the number of spanning trees in the graph is maximised. We investigate the effective graph resistance (also known as the Kirchhoff index), which was proposed as robustness metric in [ 11 ] . The NP-hardness of k -GRIP for the effective graph resistance was proven in [ 19 ] . Summers et al . [ 35 ] attempted to prove that k -GRIP with the effective graph resistance is submodular. Later, they corrected their own statement in an online document [ 34 ] , showing a counterexample for submodularity. Nevertheless, the greedy algorithm appears to yield near-optimal solutions. Wang et al . [ 39 ] considered adding a single link and derived bounds for the quality of the greedy algorithm. They additionally investigated different strategies to find the optimal link to add. Pizzuti and Socievole [ 26 ] introduce a genetic algorithm as a heuristic to find the best link to add. Clemente and Cornaro [ 9 ] derived bounds for the effective graph resistance after adding/removing one or multiple links. Ghosh et al . [ 15 ] considered the case of weighted links, under a fixed allocation budget, for which an efficient (polynomial-time) algorithm is provided. Etesami [ 12 ] and Chan et al . [ 4 ] consider maximising and minimizing the effective graph resistance between source node s and target node t under a fixed allocation budget, respectively. Results for k -GRIP may, besides the considered robustness metric, also depend on the optimisation problem itself. For example, [ 8 , 6 , 7 ] consider a node-selection optimisation problem with the effective graph resistance as robustness metric, whereas k -GRIP considers link addition with the effective graph resistance, which is fundamentally different. Even though the objective function is the same (minimising the effective graph resistance), the problem constraints are very different. In their case, submodularity of the effective graph resistance holds, whereas in our case, we prove that the considered problem does not even satisfy the condition of generalized submodularity. 3 Background In this paper we consider undirected, connected simple graphs G=(V,E) without self-loops. Here V denotes the set of N vertices, while E is the set of L links connecting vertex pairs of V . The notation i\sim j indication that nodes i and j are adjacent in G . We let G^{c}=(V,E^{c}) denote the complementary graph of G , where E^{c}=\{(u,v)|u,v\in V,u\neq v,(u,v)\not\in E\} . The adjacency matrix A of G is an N\times N symmetric matrix with elements a_{ij} that are either 1 or 0 depending on whether there is a link between nodes i and j or not. The Laplacian matrix Q of G is an N\times N symmetric matrix Q=\Delta-A , where \Delta=diag(d_{i}) is the N\times N diagonal degree matrix with the elements d_{i}=\sum_{j=1}^{N}a_{ij} . The eigenvalues of Q are all real and non-negative and can be ordered as 0=\mu_{1}\leq\mu_{2}\leq\cdots\leq\mu_{N} . Interpreting the graph G as an electrical network whose edges are resistors of 1\Omega , the effective resistance \omega_{ij} between node i and j can be computed based on Kirchoff’s circuit laws, where it assumed that a unit current is injected into G at i and extracted at j . Then the effective graph resistance R_{G} , also known as the Kirchhoff index , is defined as the sum of the effective resistances over all node pairs [ 18 ] : R_{G}(G)=\sum_{1\leq ir_{G,\textnormal{opt}} then 8: W_{\textnormal{opt}}\leftarrow W_{j} 9: r_{G,\textnormal{opt}}\leftarrow r_{G}(G_{i}\cup\{W_{j}\}) 10: end if 11: end for 12: G_{i+1}\leftarrow G_{i}\cup\{V_{\textnormal{opt}}\} 13: W\leftarrow W\backslash W_{j} 14: end for 15: Output: G_{k+1} Because r_{G} is not submodular, the performance bound of [ 24 ] , i.e. the (1-\frac{1}{e}) -closeness of the greedy solution to the optimal one, is not guaranteed. However, the following result can be used for non-submodular functions: Theorem 6 ( [ 2 ] ) . Let f be a monotonically increasing, nonnegative function with submodularity ratio \gamma\in[0,1] and curvature \alpha\in[0,1] . Then the greedy Algorithm 1 has the following guaranteed solution quality: f_{\textnormal{greedy}}\geq\frac{1}{\alpha}\left(1-e^{-\gamma\alpha}\right)f_{\textnormal{optimal}} (4) Here, the curvature \alpha is defined as follows: Definition 7 ( [ 2 ] ) . The curvature \alpha of a function f on a set W is the smallest \alpha in the interval [0,1] that satisfies f(S\cup\Omega)-f((S\backslash v)\cup\Omega)\geq(1-\alpha)(f(S)-f(S\backslash v)) for all \Omega,S\subset W and all v\in S\backslash\Omega . The curvature \alpha quantifies how close f is to being supermodular. A function is called supermodular if -f is submodular, where supermodularity corresponds to \alpha=0 . Recently [ 21 ] improved the result in Theorem 6 as follows: f_{\textnormal{greedy}}\geq(1-(1-\gamma+\gamma\alpha)e^{-\gamma})f_{\textnormal{optimal}} (5) Note that for \alpha=1 and \gamma=1 , Eqs. ( 4 )–( 5 ) both lead to the performance guarantee provided by the submodularity condition. In case \gamma=0 , the Eqs. ( 4 )–( 5 ) both simplify to f_{\textnormal{greedy}}\geq 0 , which does not provide any performance guarantee, because it was already assumed that f was nonnegative. Note that for f\equiv r_{G} and by using Eq. ( 3 ), f_{\textnormal{greedy}}\geq 0 is equivalent to R_{G}\leq\binom{N-1}{3} , which indeed does not provide any new insight because it is already known that for connected graphs \binom{N-1}{3} is an upper bound for R_{G} . In this paper we will construct a family of graphs for which \gamma\to 0 for N\to\infty . 4 A counterexample for generalized submodularity Summers et al . [ 34 ] have already shown that the normalized effective graph resistance r_{G} does not satisfy submodularity (see Definition 3 ). Their counterexample, which is also the smallest possible counterexample, is a graph with N=5 nodes shown in Fig. 1 . Starting point is a graph G with 5 nodes and 5 links, denoted as solid black lines. The set S is the empty set, while the element v is the link between nodes 1 and 2, represented by a dashed green line. The set R is the link between nodes 2 and 3, represented by a dotted red line. To compute \gamma for this case we need to determine the ratio of r_{G}(G\cup\{v\})-r_{G}(G) and r_{G}(G\cup R\cup\{v\})-r_{G}(G\cup R) . Using Eq. ( 3 ), this comes down to computing the ratio between R_{G}(G)-R_{G}(G\cup\{v\}) and R_{G}(G\cup R)-R_{G}(G\cup R\cup\{v\}) . Evaluation of the 4 involved expressions gives R_{G}(G)\approx 13.33,R_{G}(G\cup\{v\})=10.25,R_{G}(G\cup R)=10.25 and R_{G}(G\cup R\cup\{v\})\approx 6.95 . Thus the gain of adding the element v (the dashed green link) to the original graph (the graph G ) is approximately equal to 13.33-10.25=3.08 while adding the element v to the augmented graph (the graph G with the link R added), gives a larger gain of approximately 10.25-6.95=3.30 . Clearly this opposes the definition of submodularity. Thus, k -GRIP for the normalized effective graph resistance is not submodular. We can also deduce from the example that \gamma\lesssim\frac{3.08}{3.30}=0.935 . 1 2 3 4 5 Figure 1: The smallest counterexample showing that the normalized effective graph resistance r_{G} in k -GRIP is not submodular. The graph G consists of 5 nodes with 5 links, denoted as solid black lines. The set S is the empty set, while the element v is the link between nodes 1 and 2, represented by a dashed green line. The set R is the link between nodes 2 and 3, represented by a dotted red line. This result can be improved by showing that the normalized effective graph resistance even does not satisfy generalised submodularity. It is sufficient to construct a counterexample where \gamma\to 0 . As a consequence, Eqs. ( 4 )–( 5 ) then imply that the greedy solution does not have any guaranteed performance. To construct a counterexample we consider a graph G on 2N nodes, N\geq 4,N even. We start building the graph G by first considering a complete bipartite graph K_{2,N-2} on N nodes. We define node i and j to be the nodes in the group with 2 nodes. Then, we select two nodes from the group with N-2 nodes and attach a path graph of length N/2 to each of those nodes. The resulting graph G is depicted in Fig. 2a . Again, we assume the set S is the empty set. The element v is taken to be the link between node i and j , as visualised in Fig. 2b , represented by a dashed green line. The set R contains two links: we connect the end of one path graph to node i and the end of the other path graph to node j . The links in the set R are represented by dotted red lines, see Fig. 2c . Finally, Fig. 2d shows graph G augmented with the sets R and v . i j (a) G i j (b) G\cup\{v\} i j (c) G\cup R i j (d) G\cup R\cup\{v\} Figure 2: The graph G consisting of 2N nodes; two path graphs with N/2 nodes are attached to a complete bipartite graph K_{2,N-2} on N nodes. The element v is the dashed green link in the complete bipartite graph between node i and j . The set R , represented by dotted red links, is the union of the link connecting node i with the left-most node of the graph and the link connecting node j with the right-most node of the graph. In this example, N=6 . We now present our main results. Theorem 8 . Consider the graph G depicted in Fig. 2 , the element v and the set R . Then the following holds R_{G}(G)-R_{G}(G\cup\{v\})=\frac{4}{N-2} (6) and R_{G}(G\cup R)-R_{G}(G\cup R\cup\{v\})=\frac{2\,(N+3)\,(N+4)\,(N+5)}{3\,(N+1)\,(N+2)\,(N^{2}+N-4)} (7) Proof. See Appendix A . ∎ Theorem 9 . Consider the graph G depicted in Fig. 2 . Then the submodularity ratio for k -GRIP for the normalized effective graph resistance r_{G} satisfies \gamma\leq\frac{6\,(N+1)\,(N+2)\,(N^{2}+N-4)}{(N-2)\,N\,(N+3)\,(N+4)\,(N+5)} (8) which, for large N converges to zero. In other words, the normalized effective graph resistance r_{G} is not generalised submodular and the accuracy bounds from Eqs. ( 4 )–( 5 ) do not provide any guaranteed performance for the greedy algorithm. Proof. We already observed that in order to estimate \gamma for the normalized effective graph resistance we need to determine the ratio of r_{G}(G\cup\{v\})-r_{G}(G) and r_{G}(G\cup R\cup\{v\})-r_{G}(G\cup R) , which equals the ratio between R_{G}(G)-R_{G}(G\cup\{v\}) and R_{G}(G\cup R)-R_{G}(G\cup R\cup\{v\}) , according to Eq. ( 3 ). Hence, Eq. ( 8 ) follows from Eqs. ( 6 )–( 7 ). ∎ Note that the right-hand side of Eq. ( 8 ) asymptotically behaves as 6/N . Fig. 3 depicts the exact upper bound for \gamma and its asymptote. For 2N\geq 100 , both curves are nearly indistinguishable. Figure 3: The upper bound for the submodularity ratio \gamma according to Eq. ( 8 ) and its asymptote 6/N for various values of N . 5 The quality of the greedy algorithm The counterexample from Theorem 9 demonstrates that the quality of the greedy solution cannot be guaranteed. However, this does not necessarily imply that the greedy algorithm actually performs bad . Instead, we just cannot guarantee the quality of the greedy algorithm. In this section, we measure the performance of the greedy algorithm. We define the efficiency \eta as \eta=\frac{(R_{G})_{\textnormal{opt}}}{(R_{G})_{\textnormal{greedy}}} If the efficiency \eta=1 , the greedy algorithm provides the optimal solution. If the efficiency \eta<1 , the greedy algorithm produces a sub-optimal solution. We determine the accuracy of the greedy algorithm by looking at small graphs. We consider 2\leq k\leq 6 links to be added by the greedy algorithm, which we then compare with the optimal value, which we obtain by brute-force. For k=1 , the optimal and the greedy algorithm coincide. We generate all non-isomorphic, connected graphs using Nauty and Traces [ 22 ] . Out of all non-isomorphic connected graphs, we compute the smallest efficiency \eta_{\min} for 5\leq N\leq 10 and 2\leq k\leq 6 , which are shown in Table 1 . The computational complexity equals \mathcal{O}(kL^{c}N^{3}) for the greedy algorithm and \mathcal{O}((L^{c})^{k}N^{3}) for the brute-force algorithm, implying that the procedure can only be executed for small graphs. We verified all graphs with N\leq 8 nodes and randomly selected several graphs for N=9,N=10 . The worst case, corresponding to the graph shown in Fig. 4 with N=10 nodes and k=3 added links, has efficiency \eta=\mathbf{0.878} , implying that the greedy algorithm produces a graph whose effective graph resistance is a factor 0.878 different from the optimal effective graph resistance. Already for a small graph with N=10 nodes, the efficiency \eta is quite low. We expect that larger graphs may have even lower efficiencies, but the computational complexity is too demanding to demonstrate that here. Table 1: The lowest efficiency \eta_{\min} for each possible combination of the number of nodes N and the number of added links k . The values for N=9,10 are lower bounds, as the number of non-isomorphic graphs is too large to compute all; instead, we randomly selected several graphs. The lowest efficiency \eta_{\min} is highlighted in bold . N=5 N=6 N=7 N=8 N=9 N=10 k 21 graphs 112 graphs 853 graphs 11,117 graphs 261,080 graphs 11,716,571 graphs 2 0.937 0.946 0.934 0.922 0.891 \leq 0.905 3 1 0.957 0.940 0.931 0.913 \mathbf{\leq 0.878} 4 1 0.957 0.949 0.936 0.899 \leq 0.918 5 1 0.965 0.966 0.949 \leq 0.919 \leq 0.918 6 1 0.970 0.966 0.950 \leq 0.941 \leq 0.932 1 2 3 4 5 6 7 8 9 10 (a) Original 1 2 3 4 5 6 7 8 9 10 (b) Optimal 1 2 3 4 5 6 7 8 9 10 (c) Greedy Figure 4: The graph G with the currently known smallest efficiency \eta_{\min}=0.878 on N=10 nodes and the k=3 added links are shown as dashed green links. 6 Conclusion We consider the optimisation problem of adding k links to a given network, such that the resulting normalized effective graph resistance is as large as possible. We have shown that this problem is not generalised submodular, by providing an example for which the submodularity ratio converges to zero. As a consequence, we have no guaranteed solution quality of the greedy algorithm. We additionally investigate the efficiency of the greedy algorithm for optimizing the effective graph resistance for small graphs. Already for graphs with 10 nodes, the efficiency can be as low as 0.878 . On the agenda for future research is finding an example where the performance of the greedy algorithm is even lower. One possible method is to consider a class of graphs which, for a given number of nodes N and number of links L , have optimal effective graph resistance. Then we start with another graph with N nodes and a subset of the links in the first graph. By sequentially adding links using the greedy algorithm, the graph may converge to the optimum, or if otherwise, we may find explicit examples for the efficiency smaller than one in large graphs. Alternatively, one can derive alternative lower bounds on the solution quality of the greedy algorithm. Appendix A Proof of Theorem 8 Prior to our proof, we first present two powerful theorems. Theorem 10 (Theorem 2.1 from [ 40 ] ) . Let \omega and \omega^{\prime} be resistance distance functions for connected graphs G and G^{\prime} which are the same except for the weights w and w^{\prime} on an link with nodes i and j . Introduce \delta=w^{\prime}-w . Then for any nodes p\neq q it holds that \omega^{\prime}_{pq}=\omega_{pq}-\frac{\delta\cdot\left[\omega_{p,i}+\omega_{q,j}-\omega_{p,j}-\omega_{q,i}\right]^{2}}{4[1+\delta\omega_{ij}]} (9) Theorem 11 (Theorem 4.1 from [ 40 ] ) . Let \omega and \omega^{\prime} be resistance distance functions for connected, weighted graphs G and G^{\prime} on \tilde{N} nodes which are the same, except for the weights w and w^{\prime} on an link with node i and j . Introduce \delta=w^{\prime}-w . Then R_{G}(G)-R_{G}(G^{\prime})=\frac{\delta\tilde{N}\sum_{k=1}^{\tilde{N}}(\omega_{ik}-\omega_{jk})^{2}-\delta\left[\sum_{k=1}^{\tilde{N}}\omega_{ik}-\sum_{k=1}^{\tilde{N}}\omega_{jk}\right]^{2}}{4(1+\delta\omega_{ij})} (10) A.1 The graphs G and G\cup\{v\} The graph G is a graph on 2N nodes. The graph can be constructed from a complete bipartite graph K_{2,N-2} as follows. Select two nodes from the group with N-2 nodes and attach to each of these nodes a path graph of length N/2 . Now denote the two nodes that belong to the group consisting of two nodes only, as node i and j . The element v is the link between node i and j . For a visualisation, see Fig. 5 . i j Figure 5: The original graph G . The element v is the dashed green link between node i and j . We directly apply Theorem 10 with \delta=1 and \tilde{N}=2N , where the graph G is considered the “original graph” and graph G^{\prime} is graph G augmented with v . Then we find R_{G}(G)-R_{G}(G\cup\{v\})=\frac{2N\sum_{k=1}^{2N}(\omega_{ik}-\omega_{jk})^{2}-\left[\sum_{k=1}^{2N}\omega_{ik}-\sum_{k=1}^{2N}\omega_{jk}\right]^{2}}{4(1+\omega_{ij})} (11) Due to symmetry, we can immediately conclude that the second term is zero. Moreover, \omega_{ik}=\omega_{jk} for all k\leq i and k\neq j , again due to symmetry. Eq. ( 11 ) then simplifies to R_{G}(G)-R_{G}(G\cup\{v\})=\frac{N\omega_{ij}^{2}}{1+\omega_{ij}} (12) Since \omega_{ij} is not affected by the path graphs, the question of finding \omega_{ij} simplifies to finding the effective resistance between two nodes in the complete bipartite graph K_{2,N-2} . Using the theory of parallel and series resistors, we find that \omega_{ij}=\frac{2}{N-2} and conclude that R_{G}(G)-R_{G}(G\cup\{v\})=\frac{4}{N-2} (13) A.2 The graphs G\cup R and G\cup R\cup\{v\} The set R consists of two links. From node i , we add one link to the end of a path graph, i,e, the left-most node of graph G and perform the same procedure to node j . The resulting graph G\cup R is shown in Fig. 6 . i j m l N/2 k 1 Figure 6: The augmented graph G\cup R , which contains the original graph G and the set R , denoted by dotted red links. We now return to Theorem 10 with \delta=1 and \tilde{N}=2N , where the graph G\cup R is considered the “original graph”. Then we find R_{G}(G\cup R)-R_{G}(G\cup R\cup\{v\})=\frac{2N\sum_{k=1}^{2N}(\omega_{ik}-\omega_{jk})^{2}-\left[\sum_{k=1}^{2N}\omega_{ik}-\sum_{k=1}^{2N}\omega_{jk}\right]^{2}}{4(1+\omega_{ij})} (14) The second term is again zero due symmetry. Then the equation simplifies to \Delta R_{G}=\frac{2N}{4(1+\omega_{ij})}\sum_{k=1}^{2N}(\omega_{ik}-\omega_{jk})^{2} (15) In order to determine \Delta R_{G} we need to find expressions for the effective resistance \omega_{ij},\omega_{ik} and \omega_{jk} for the graph G\cup R . Note that the graph R is planar, as can be seen from Fig. 7 , which shows the graph G\cup R drawn without intersecting links. i j m l N/2 k 1 Figure 7: The graph G\cup R redrawn as a planar graph. Because G\cup R is planar, according to [ 36 ] , it is possible to determine the effective resistance for each node pair by a sequence of series, parallel, Y-\Delta , and \Delta-Y transformations. To analyse Eq. ( 15 ) it is convenient to consider the following two subsets of nodes in the graph G\cup R . First, denote the nodes in K_{2,N-2} attached to the two path graphs as nodes l and m , see Fig. 6 . Then we define the node set A as the nodes in K_{2,N-2} minus the nodes i , j , l and m . Hence, A consists of N-4 nodes. Next, the subset of nodes B is formed by the nodes in the two path graphs plus the nodes l and m . Therefore, set B contains N+2 nodes. We can now split up the sum in Eq. ( 15 ) into three parts; (i) terms containing only \omega_{ij} (2x), (ii) terms containing only nodes in set A (iii) terms containing only nodes in set B . Then Eq. ( 15 ) becomes \Delta R_{G}=\frac{2N}{4(1+\omega_{ij})}\left(2\omega_{ij}^{2}+\sum_{k\in A}(\omega_{ik}-\omega_{jk})^{2}+\sum_{k\in B}(\omega_{ik}-\omega_{jk})^{2}\right) In the complete bipartite graph K_{2,N-2} , due to symmetry, it holds that \omega_{ik}=\omega_{jk} , so the contribution of set A is zero. Thus, we can simplify \Delta R_{G} to \Delta R_{G}=\frac{2N}{4(1+\omega_{ij})}\left(2\omega_{ij}^{2}+\sum_{k\in B}(\omega_{ik}-\omega_{jk})^{2}\right) (16) Hence, we need to compute \omega_{ij} and \omega_{ik} and \omega_{jk} for nodes k in the path graph. The index k runs from k=1 to k=N/2+1 , where the index k=N/2+1 corresponds to node l , see Fig. 6 . As a first simplification step, we apply the resistors in series transformation twice, to the left part of the graph G\cup R in Fig. 6 . We replace the path i,1,\cdots,k by a single resistor of value k and the path i,l,N/2,\cdots,k by a single resistor of value (\frac{N}{2}-k+1) . The result is depicted in Fig. 8 . i j m l k k \frac{N}{2}-k+1 Figure 8: Result of simplification step 1 on the graph G\cup R . Next we apply the series transformation to the path from node j to m on the right part of the graph, to obtain a link with a resistance of \frac{N}{2}+1 . This results in two links between nodes j and m . Applying the transformation for parallel resistors to these two links, we obtain a single link between nodes j and m , with the following resistance: r_{jm}=\frac{1}{1+\frac{1}{\frac{N}{2}+1}}=\frac{N+2}{N+4} The resulting graph is depicted in Fig. 9 . i j m l k \frac{N+2}{N+4} k \frac{N}{2}-k+1 Figure 9: Result of simplification step 2 on the graph G\cup R . In Fig. 9 there are N-2 two-hop paths between nodes i and j . Excluding the two paths passing through nodes l and m , we can use the parallel resistors transformation to transform the remaining N-4 two-hop paths to a single link between nodes i and j , with resistance r_{ij} given by r_{ij}=\frac{1}{\frac{1}{2}(N-4)}=\frac{2}{N-4} The resulting graph is depicted in Fig. 10 i j m l k 1 1 \frac{N+2}{N+4} 1 k \frac{N}{2}-k+1 \frac{2}{N-4} Figure 10: Result of simplification step 3 on the graph G\cup R . Next, we replace the path i,m,j by a single link of resistance 1+\frac{N+2}{N+4} . Then, again using the parallel resistors transformation between nodes i and j , the resistance r_{ij}^{\prime} on the link (i,j) becomes r_{ij}^{\prime}=\dfrac{1}{\dfrac{1}{\dfrac{2}{N-4}}+\dfrac{1}{1+\dfrac{N+2}{N+4}}}=\frac{2N+6}{N^{2}-8} The resulting graph is depicted in Fig. 11 . i j l k \frac{2N+6}{N^{2}-8} 1 1 k \frac{N}{2}-k+1 Figure 11: Result of simplification step 4 on the graph G\cup R With the graph shown in Fig. 11 we will now compute the resistances \omega_{ij},\omega_{ik} and \omega_{jk} . Resistance \omega_{ij} between node i and j : The links (i,k) and (k,l) in series, are parallel to the link (i,l) , such that we can replace the three links by a single link with resistance r_{il} , given by r_{il}=\frac{N+2}{N+4} The resulting graph is depicted in Fig. 12 i j l \frac{2N+6}{N^{2}-8} \frac{N+2}{N+4} 1 Figure 12: Result of simplification step 5a on the graph G\cup R In the graph shown in Fig. 12 the links (i,l) and (l,j) in series, are parallel to the link (i,j) , such that we can replace the three links by a single link so we finally obtain the resistance \omega_{ij} : \omega_{ij}=\frac{2N+6}{N^{2}+N-4} (17) a Resistance \omega_{ik} between node i and k : In Fig. 11 the links (i,j) and (j,l) in series, are parallel to the link (i,l) , such that we can replace the three links by a single link with resistance r_{il}^{\prime} , given by r_{il}^{\prime}=\frac{N^{2}+2N-2}{2N^{2}+2N-10} The resulting graph is shown in Fig. 13 . i l k \frac{N^{2}+2N-2}{2N^{2}+2N-10} k \frac{N}{2}-k+1 Figure 13: Result of simplification step 5b on the graph G\cup R In the graph shown in Fig. 13 the links (i,l) and (l,k) in series, are parallel to the link (i,k) , such that we can replace the three links by a single link so we finally obtain the resistance \omega_{ik} : \omega_{ik}=\frac{k(-2kN^{2}-2kN+10k+N^{3}+4N^{2}-N-12)}{(N+3)(N^{2}+N-4)} (18) a Resistance \omega_{jk} between node j and k : For this case, the series and parallel transformations do not work. Instead, we use the \Delta-Y transform on the right-hand side triangle in the graph in Fig. 11 . This comes down to removing the links (i,j),(i,l) and (j,l) , adding a new node A to the graph, and adding links (i,A),(j,A) and (l,A) , with resistance \frac{a}{2+a} , \frac{a}{2+a} , and \frac{1}{2+a} , respectively, where a=\frac{2N+6}{N^{2}-8} . The resulting graph is depicted in Fig. 14 . i j l k A \frac{a}{2+a} \frac{a}{2+a} \frac{1}{2+a} k \frac{N}{2}-k+1 Figure 14: Result of simplification step 5c on the graph G\cup R . Now series and parallel transformations can be applied to obtain \omega_{jk}=-\frac{18+12N+2N^{2}-24k-5Nk+4N^{2}k+N^{3}k+10k^{2}-2Nk^{2}-2N^{2}k^{2}}{12+N-4N^{2}-N^{3}} Having established \omega_{ij},\omega_{ik} and \omega_{jk} , we compute \omega_{ik}-\omega_{jk}=\frac{2(2k-N-3)}{N^{2}+N-4} where the index 1\leq k\leq\frac{N}{2}+1 . Then we find \sum_{k=1}^{N/2+1}\left(\omega_{ik}-\omega_{jk}\right)^{2}=\frac{2(N^{3}+6N^{2}+11N+6)}{3(N^{2}+N-4)^{2}} (19) Substituting Eqs. ( 17 )–( 19 ) into Eq. ( 16 ) finally gives \Delta R_{G}=\frac{2N(N^{3}+12N^{2}+47N+60)}{3(N^{4}+4N^{3}+N^{2}-10N-8)}=\frac{2\,(N+3)\,(N+4)\,(N+5)}{3\,(N+1)\,(N+2)\,(N^{2}+N-4)} (20) Then the relative difference for the graph G provided in Eq. ( 13 ) and for the graph G\cup R in Eq. ( 20 ) finally yields \gamma\leq\frac{6\,(N+1)\,(N+2)\,(N^{2}+N-4)}{(N-2)\,N\,(N+3)\,(N+4)\,(N+5)} For large N , we see that \gamma\sim\frac{6}{N} , which converges to zero.