M each edge e resistance Re =1 Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) Vu,V,E V,Tu,v Tv,u 2mR(u,U) d(u) d(x) du)】 d(x) A: B: 2m4 d() d(y) d(y) d(v)
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) 8u, v, 2 V, ⌧u,v + ⌧v,u = 2mR(u, v) 23-2 Lecture 23: November 17 Notes 1. The above two algorithms demonstrate a time-space tradeo↵, in that the product of space and time remains constant. In fact, it turns out that there is a whole spectrum of randomized algorithms spanning this tradeo↵ [F97]: 8s 9 algorithm using space s and time O˜(|V ||E| s ) that visits all (reachable) vertices w.h.p. (The notation O˜ hides logarithmic as well as constant factors.) 2. In an important breakthrough, Reingold [R05] showed that the above random walk algorithm could be derandomized, thus obtaining a deterministic O(1) space algorithm for graph searching (phrased more precisely as testing whether there is a path between a given pair of vertices u, v. More correctly this is a O(log n) space algorithm, since O(log n) space is needed to record the label of a vertex in an n-vertex graph, and to keep track of the number of steps taken so far.) Since the connectivity problem is a canonical problem solvable in randomized log-space, this seems like a major step towards proving that every randomized log-space algorithm can be derandomized with only a constant factor penalty in space. However, this question remains open (see, e.g., [RTV06] for some interesting approaches). We should also observe that the analogous question for directed graphs is much more challenging, since testing connectivity in this case is a complete problem for non-deterministic log-space. Thus a deterministic (or even randomized) log-space algorithm for it would show that even non-determinism buys us nothing in the world of log-space algorithms. One problem here is that the naive random walk approach breaks down because the cover time on directed graphs can be exponentially large. The bound on the cover time comes from the following theorem, originally due to Aleliunas et al. [AKLLR79]. Theorem 23.4 For any connected graph G, C(G) 2|E||V |. We will follow a di↵erent route due to Chandra et al. [CRRST89], which is based on an intriguing connection between random walks and electrical networks. Along the way, we will also obtain bounds on hitting times. 23.2 Hitting time and commute time To prove theorem 23.4, we start by proving some properties of the hitting time for a vertex. To do this, we will view the graph as an electrical network, where each edge has unit resistance. (For a detailed treatment of the relationship between random walks and electrical networks, see the classic book by Doyle and Snell [DS84].) When a potential di↵erence is applied between nodes of this network from an external source, current flows in the network in accordance with Kircho↵’s Laws and Ohm’s Laws: • K1: The total current into and out of a vertex is equal to zero. • K2: The sum of potential di↵erences around any cycle is zero. • Ohm’s Law: The current flowing along any edge is equal to pot. di↵erence resistance . u each edge e resistance Re = 1 Lecture 23: November 17 23-3 Figure 23.1: Graph as an electrical network Definition 23.5 The e↵ective resistance R(u, v) between two nodes u and v is the potential di↵erence between u and v that is required to send one unit of current from u to v. Now we prove a few useful lemmas about hitting times. Consider first Scenario A, in which we inject d(x) units of current into each node x, and remove all 2m = P x d(x) units of current from node v, where d(x) denotes the degree of x. (See Figure 23.2.) Lemma 23.6 The potential di↵erence u,v between v and any other node u in Scenario A satisfies u,v = Hu,v. Figure 23.2: Scenario A Proof: Consider any vertex u 2 V . Using Kircho↵’s Laws and Ohm’s Law, we have d(u) = X (u,x)2E (current u ! x) (K1) = X (u,x)2E u,x (Ohm) = X (u,x)2E (u,v x,v) (K2) = d(u)u,v X (u,x)2E x,v. Rearranging thus gives u,v =1+ 1 d(u) X (u,x)2E x,v. (23.1) On the other hand, consider the random walk starting from u. Thinking of just the first step of this walk, we see that the hitting time Hu,v satisfies Hu,v =1+ 1 d(u) X (u,x)2E Hx,v. But this is exactly the same system of linear equations as (23.1), satisfied by u,v. Since we know that this system has a unique solution (the potentials are uniquely determined by the current flows), we deduce that Hu,v = u,v 8u, v 2 V. 23-4 Lecture 23: November 17 We now use Lemma 23.6 to deduce a more useful result that expresses the commute time Hu,v + Hv,u precisely in terms of the e↵ective resistance. (Note that the commute time, unlike the hitting time, is a symmetric quantity.) Lemma 23.7 For all u,v, the commute time Hu,v + Hv,u = 2mRu,v. Proof: The proof makes use of Scenario B, which is like Scenario A except that we remove the 2m units of current from node u instead of from node v. Denoting potential di↵erences in Scenario B by 0 , we have, by Lemma 23.6, 0 v,u = Hv,u. Now consider Scenario C, which is like Scenario B but with all the currents reversed. Denoting potential di↵erences in this scenario by 00, we thus have 00 u,v = 0 v,u = Hv,u. Scenario B Scenario C Scenario D Figure 23.3: Scenarios B, C and D Finally, consider Scenario D, which is just the sum of Scenarios A and C. By linearity, and denoting potential di↵erences in Scenario D by 000, we have 000 u,v = u,v + 00 u,v = Hu,v + Hv,u. But note that u,v is the potential di↵erence required to move 2m units of charge from u to v, so by definition it is equal to 2mRu,v. This completes the proof. Examples 1. The line graph Consider n+1 points on a line. By symmetry, H0n = Hn0. Also, H0n+Hn0 = 2mR0n = 2⇥n⇥n = 2n2. Thus, H0n = Hn0 = n2. (This is in accordance with the result we obtained earlier using the martingale optional stopping theorem.) 0 12 n−1 n A: B:
Lemma: u∈V,0u,v=Tu,u du)】 d(x) 袋效 d(v)- d(y) 2m Bw.v uw∈E has the same unique solution wu∈E
Lecture 23: November 17 23-3 Figure 23.1: Graph as an electrical network Definition 23.5 The e↵ective resistance R(u, v) between two nodes u and v is the potential di↵erence between u and v that is required to send one unit of current from u to v. Now we prove a few useful lemmas about hitting times. Consider first Scenario A, in which we inject d(x) units of current into each node x, and remove all 2m = P x d(x) units of current from node v, where d(x) denotes the degree of x. (See Figure 23.2.) Lemma 23.6 The potential di↵erence u,v between v and any other node u in Scenario A satisfies u,v = Hu,v. Figure 23.2: Scenario A Proof: Consider any vertex u 2 V . Using Kircho↵’s Laws and Ohm’s Law, we have d(u) = X (u,x)2E (current u ! x) (K1) = X (u,x)2E u,x (Ohm) = X (u,x)2E (u,v x,v) (K2) = d(u)u,v X (u,x)2E x,v. Rearranging thus gives u,v =1+ 1 d(u) X (u,x)2E x,v. (23.1) On the other hand, consider the random walk starting from u. Thinking of just the first step of this walk, we see that the hitting time Hu,v satisfies Hu,v =1+ 1 d(u) X (u,x)2E Hx,v. But this is exactly the same system of linear equations as (23.1), satisfied by u,v. Since we know that this system has a unique solution (the potentials are uniquely determined by the current flows), we deduce that Hu,v = u,v 8u, v 2 V. Lemma: 8u 2 V, u,v = ⌧u,v =1+ 1 d(u) X wu2E ⌧w,v u,v =1+ 1 d(u) X uw2E w,v ⌧u,v ) has the same unique solution
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) Vu,V,E V,Tu,v +Tv,u 2mR(u,v) du】 d(x) d(u) d(x) A: B: 州双 2m d() d(y) d(y) 2m d() u,U Tu,v U,u Tv,u
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) 8u, v, 2 V, ⌧u,v + ⌧v,u = 2mR(u, v) Lecture 23: November 17 23-3 Figure 23.1: Graph as an electrical network Definition 23.5 The e↵ective resistance R(u, v) between two nodes u and v is the potential di↵erence between u and v that is required to send one unit of current from u to v. Now we prove a few useful lemmas about hitting times. Consider first Scenario A, in which we inject d(x) units of current into each node x, and remove all 2m = P x d(x) units of current from node v, where d(x) denotes the degree of x. (See Figure 23.2.) Lemma 23.6 The potential di↵erence u,v between v and any other node u in Scenario A satisfies u,v = Hu,v. Figure 23.2: Scenario A Proof: Consider any vertex u 2 V . Using Kircho↵’s Laws and Ohm’s Law, we have d(u) = X (u,x)2E (current u ! x) (K1) = X (u,x)2E u,x (Ohm) = X (u,x)2E (u,v x,v) (K2) = d(u)u,v X (u,x)2E x,v. Rearranging thus gives u,v =1+ 1 d(u) X (u,x)2E x,v. (23.1) On the other hand, consider the random walk starting from u. Thinking of just the first step of this walk, we see that the hitting time Hu,v satisfies Hu,v =1+ 1 d(u) X (u,x)2E Hx,v. But this is exactly the same system of linear equations as (23.1), satisfied by u,v. Since we know that this system has a unique solution (the potentials are uniquely determined by the current flows), we deduce that Hu,v = u,v 8u, v 2 V. 23-4 Lecture 23: November 17 We now use Lemma 23.6 to deduce a more useful result that expresses the commute time Hu,v + Hv,u precisely in terms of the e↵ective resistance. (Note that the commute time, unlike the hitting time, is a symmetric quantity.) Lemma 23.7 For all u,v, the commute time Hu,v + Hv,u = 2mRu,v. Proof: The proof makes use of Scenario B, which is like Scenario A except that we remove the 2m units of current from node u instead of from node v. Denoting potential di↵erences in Scenario B by 0 , we have, by Lemma 23.6, 0 v,u = Hv,u. Now consider Scenario C, which is like Scenario B but with all the currents reversed. Denoting potential di↵erences in this scenario by 00, we thus have 00 u,v = 0 v,u = Hv,u. Scenario B Scenario C Scenario D Figure 23.3: Scenarios B, C and D Finally, consider Scenario D, which is just the sum of Scenarios A and C. By linearity, and denoting potential di↵erences in Scenario D by 000, we have 000 u,v = u,v + 00 u,v = Hu,v + Hv,u. But note that u,v is the potential di↵erence required to move 2m units of charge from u to v, so by definition it is equal to 2mRu,v. This completes the proof. Examples 1. The line graph Consider n+1 points on a line. By symmetry, H0n = Hn0. Also, H0n+Hn0 = 2mR0n = 2⇥n⇥n = 2n2. Thus, H0n = Hn0 = n2. (This is in accordance with the result we obtained earlier using the martingale optional stopping theorem.) 0 12 n−1 n A: B: A u,v = ⌧u,v B v,u = ⌧v,u
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) Vu,V,E V,Tu,v To,u 2mR(u,V) A: d(x) B: d(x) d(x) (u) V/ 2m 2m d(v)- d(y) d(y) d(y) 2m d(v) d() A u,U Tu,v 二 Tv,u uv= Tv,u D D=A+C 2m =Tu,v Tv,u potential difference between u and v 2m to send 2m units current flow from u to v
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) 8u, v, 2 V, ⌧u,v + ⌧v,u = 2mR(u, v) Lecture 23: November 17 23-3 Figure 23.1: Graph as an electrical network Definition 23.5 The e↵ective resistance R(u, v) between two nodes u and v is the potential di↵erence between u and v that is required to send one unit of current from u to v. Now we prove a few useful lemmas about hitting times. Consider first Scenario A, in which we inject d(x) units of current into each node x, and remove all 2m = P x d(x) units of current from node v, where d(x) denotes the degree of x. (See Figure 23.2.) Lemma 23.6 The potential di↵erence u,v between v and any other node u in Scenario A satisfies u,v = Hu,v. Figure 23.2: Scenario A Proof: Consider any vertex u 2 V . Using Kircho↵’s Laws and Ohm’s Law, we have d(u) = X (u,x)2E (current u ! x) (K1) = X (u,x)2E u,x (Ohm) = X (u,x)2E (u,v x,v) (K2) = d(u)u,v X (u,x)2E x,v. Rearranging thus gives u,v =1+ 1 d(u) X (u,x)2E x,v. (23.1) On the other hand, consider the random walk starting from u. Thinking of just the first step of this walk, we see that the hitting time Hu,v satisfies Hu,v =1+ 1 d(u) X (u,x)2E Hx,v. But this is exactly the same system of linear equations as (23.1), satisfied by u,v. Since we know that this system has a unique solution (the potentials are uniquely determined by the current flows), we deduce that Hu,v = u,v 8u, v 2 V. 23-4 Lecture 23: November 17 We now use Lemma 23.6 to deduce a more useful result that expresses the commute time Hu,v + Hv,u precisely in terms of the e↵ective resistance. (Note that the commute time, unlike the hitting time, is a symmetric quantity.) Lemma 23.7 For all u,v, the commute time Hu,v + Hv,u = 2mRu,v. Proof: The proof makes use of Scenario B, which is like Scenario A except that we remove the 2m units of current from node u instead of from node v. Denoting potential di↵erences in Scenario B by 0 , we have, by Lemma 23.6, 0 v,u = Hv,u. Now consider Scenario C, which is like Scenario B but with all the currents reversed. Denoting potential di↵erences in this scenario by 00, we thus have 00 u,v = 0 v,u = Hv,u. Scenario B Scenario C Scenario D Figure 23.3: Scenarios B, C and D Finally, consider Scenario D, which is just the sum of Scenarios A and C. By linearity, and denoting potential di↵erences in Scenario D by 000, we have 000 u,v = u,v + 00 u,v = Hu,v + Hv,u. But note that u,v is the potential di↵erence required to move 2m units of charge from u to v, so by definition it is equal to 2mRu,v. This completes the proof. Examples 1. The line graph Consider n+1 points on a line. By symmetry, H0n = Hn0. Also, H0n+Hn0 = 2mR0n = 2⇥n⇥n = 2n2. Thus, H0n = Hn0 = n2. (This is in accordance with the result we obtained earlier using the martingale optional stopping theorem.) 0 12 n−1 n 23-4 Lecture 23: November 17 We now use Lemma 23.6 to deduce a more useful result that expresses the commute time Hu,v + Hv,u precisely in terms of the e↵ective resistance. (Note that the commute time, unlike the hitting time, is a symmetric quantity.) Lemma 23.7 For all u,v, the commute time Hu,v + Hv,u = 2mRu,v. Proof: The proof makes use of Scenario B, which is like Scenario A except that we remove the 2m units of current from node u instead of from node v. Denoting potential di↵erences in Scenario B by 0 , we have, by Lemma 23.6, 0 v,u = Hv,u. Now consider Scenario C, which is like Scenario B but with all the currents reversed. Denoting potential di↵erences in this scenario by 00, we thus have 00 u,v = 0 v,u = Hv,u. Scenario B Scenario C Scenario D Figure 23.3: Scenarios B, C and D Finally, consider Scenario D, which is just the sum of Scenarios A and C. By linearity, and denoting potential di↵erences in Scenario D by 000, we have 000 u,v = u,v + 00 u,v = Hu,v + Hv,u. But note that u,v is the potential di↵erence required to move 2m units of charge from u to v, so by definition it is equal to 2mRu,v. This completes the proof. Examples 1. The line graph Consider n+1 points on a line. By symmetry, H0n = Hn0. Also, H0n+Hn0 = 2mR0n = 2⇥n⇥n = 2n2. Thus, H0n = Hn0 = n2. (This is in accordance with the result we obtained earlier using the martingale optional stopping theorem.) 0 12 n−1 n A: B: C: A u,v = ⌧u,v B v,u = ⌧v,u C u,v = B v,u = ⌧v,u 23-4 Lecture 23: November 17 We now use Lemma 23.6 to deduce a more useful result that expresses the commute time Hu,v + Hv,u precisely in terms of the e↵ective resistance. (Note that the commute time, unlike the hitting time, is a symmetric quantity.) Lemma 23.7 For all u,v, the commute time Hu,v + Hv,u = 2mRu,v. Proof: The proof makes use of Scenario B, which is like Scenario A except that we remove the 2m units of current from node u instead of from node v. Denoting potential di↵erences in Scenario B by 0 , we have, by Lemma 23.6, 0 v,u = Hv,u. Now consider Scenario C, which is like Scenario B but with all the currents reversed. Denoting potential di↵erences in this scenario by 00, we thus have 00 u,v = 0 v,u = Hv,u. Scenario B Scenario C Scenario D Figure 23.3: Scenarios B, C and D Finally, consider Scenario D, which is just the sum of Scenarios A and C. By linearity, and denoting potential di↵erences in Scenario D by 000, we have 000 u,v = u,v + 00 u,v = Hu,v + Hv,u. But note that u,v is the potential di↵erence required to move 2m units of charge from u to v, so by definition it is equal to 2mRu,v. This completes the proof. Examples 1. The line graph Consider n+1 points on a line. By symmetry, H0n = Hn0. Also, H0n+Hn0 = 2mR0n = 2⇥n⇥n = 2n2. Thus, H0n = Hn0 = n2. (This is in accordance with the result we obtained earlier using the martingale optional stopping theorem.) 0 12 n−1 n D: D = A + C D u,v = A u,v + C u,v = ⌧u,v + ⌧v,u D u,v : potential difference between u and v to send 2m units current flow from u to v
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) Vu,V,E V,Tu,v To,u =2mR(u,V) A: u d(x) B: d(x) C·ao d(x) d(u) V/ 2mk 2m d(v)- d(y) d(y) d(y) 2m d() d() 人A u,U Tu,v 二 Tv,u P,=9 r Tv,u D D=A+C 2m =Tu,v Tv,u 2m R(u,v)= 2m
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) 8u, v, 2 V, ⌧u,v + ⌧v,u = 2mR(u, v) Lecture 23: November 17 23-3 Figure 23.1: Graph as an electrical network Definition 23.5 The e↵ective resistance R(u, v) between two nodes u and v is the potential di↵erence between u and v that is required to send one unit of current from u to v. Now we prove a few useful lemmas about hitting times. Consider first Scenario A, in which we inject d(x) units of current into each node x, and remove all 2m = P x d(x) units of current from node v, where d(x) denotes the degree of x. (See Figure 23.2.) Lemma 23.6 The potential di↵erence u,v between v and any other node u in Scenario A satisfies u,v = Hu,v. Figure 23.2: Scenario A Proof: Consider any vertex u 2 V . Using Kircho↵’s Laws and Ohm’s Law, we have d(u) = X (u,x)2E (current u ! x) (K1) = X (u,x)2E u,x (Ohm) = X (u,x)2E (u,v x,v) (K2) = d(u)u,v X (u,x)2E x,v. Rearranging thus gives u,v =1+ 1 d(u) X (u,x)2E x,v. (23.1) On the other hand, consider the random walk starting from u. Thinking of just the first step of this walk, we see that the hitting time Hu,v satisfies Hu,v =1+ 1 d(u) X (u,x)2E Hx,v. But this is exactly the same system of linear equations as (23.1), satisfied by u,v. Since we know that this system has a unique solution (the potentials are uniquely determined by the current flows), we deduce that Hu,v = u,v 8u, v 2 V. 23-4 Lecture 23: November 17 We now use Lemma 23.6 to deduce a more useful result that expresses the commute time Hu,v + Hv,u precisely in terms of the e↵ective resistance. (Note that the commute time, unlike the hitting time, is a symmetric quantity.) Lemma 23.7 For all u,v, the commute time Hu,v + Hv,u = 2mRu,v. Proof: The proof makes use of Scenario B, which is like Scenario A except that we remove the 2m units of current from node u instead of from node v. Denoting potential di↵erences in Scenario B by 0 , we have, by Lemma 23.6, 0 v,u = Hv,u. Now consider Scenario C, which is like Scenario B but with all the currents reversed. Denoting potential di↵erences in this scenario by 00, we thus have 00 u,v = 0 v,u = Hv,u. Scenario B Scenario C Scenario D Figure 23.3: Scenarios B, C and D Finally, consider Scenario D, which is just the sum of Scenarios A and C. By linearity, and denoting potential di↵erences in Scenario D by 000, we have 000 u,v = u,v + 00 u,v = Hu,v + Hv,u. But note that u,v is the potential di↵erence required to move 2m units of charge from u to v, so by definition it is equal to 2mRu,v. This completes the proof. Examples 1. The line graph Consider n+1 points on a line. By symmetry, H0n = Hn0. Also, H0n+Hn0 = 2mR0n = 2⇥n⇥n = 2n2. Thus, H0n = Hn0 = n2. (This is in accordance with the result we obtained earlier using the martingale optional stopping theorem.) 0 12 n−1 n 23-4 Lecture 23: November 17 We now use Lemma 23.6 to deduce a more useful result that expresses the commute time Hu,v + Hv,u precisely in terms of the e↵ective resistance. (Note that the commute time, unlike the hitting time, is a symmetric quantity.) Lemma 23.7 For all u,v, the commute time Hu,v + Hv,u = 2mRu,v. Proof: The proof makes use of Scenario B, which is like Scenario A except that we remove the 2m units of current from node u instead of from node v. Denoting potential di↵erences in Scenario B by 0 , we have, by Lemma 23.6, 0 v,u = Hv,u. Now consider Scenario C, which is like Scenario B but with all the currents reversed. Denoting potential di↵erences in this scenario by 00, we thus have 00 u,v = 0 v,u = Hv,u. Scenario B Scenario C Scenario D Figure 23.3: Scenarios B, C and D Finally, consider Scenario D, which is just the sum of Scenarios A and C. By linearity, and denoting potential di↵erences in Scenario D by 000, we have 000 u,v = u,v + 00 u,v = Hu,v + Hv,u. But note that u,v is the potential di↵erence required to move 2m units of charge from u to v, so by definition it is equal to 2mRu,v. This completes the proof. Examples 1. The line graph Consider n+1 points on a line. By symmetry, H0n = Hn0. Also, H0n+Hn0 = 2mR0n = 2⇥n⇥n = 2n2. Thus, H0n = Hn0 = n2. (This is in accordance with the result we obtained earlier using the martingale optional stopping theorem.) 0 12 n−1 n A: B: C: A u,v = ⌧u,v B v,u = ⌧v,u C u,v = B v,u = ⌧v,u 23-4 Lecture 23: November 17 We now use Lemma 23.6 to deduce a more useful result that expresses the commute time Hu,v + Hv,u precisely in terms of the e↵ective resistance. (Note that the commute time, unlike the hitting time, is a symmetric quantity.) Lemma 23.7 For all u,v, the commute time Hu,v + Hv,u = 2mRu,v. Proof: The proof makes use of Scenario B, which is like Scenario A except that we remove the 2m units of current from node u instead of from node v. Denoting potential di↵erences in Scenario B by 0 , we have, by Lemma 23.6, 0 v,u = Hv,u. Now consider Scenario C, which is like Scenario B but with all the currents reversed. Denoting potential di↵erences in this scenario by 00, we thus have 00 u,v = 0 v,u = Hv,u. Scenario B Scenario C Scenario D Figure 23.3: Scenarios B, C and D Finally, consider Scenario D, which is just the sum of Scenarios A and C. By linearity, and denoting potential di↵erences in Scenario D by 000, we have 000 u,v = u,v + 00 u,v = Hu,v + Hv,u. But note that u,v is the potential di↵erence required to move 2m units of charge from u to v, so by definition it is equal to 2mRu,v. This completes the proof. Examples 1. The line graph Consider n+1 points on a line. By symmetry, H0n = Hn0. Also, H0n+Hn0 = 2mR0n = 2⇥n⇥n = 2n2. Thus, H0n = Hn0 = n2. (This is in accordance with the result we obtained earlier using the martingale optional stopping theorem.) 0 12 n−1 n D: D = A + C D u,v = A u,v + C u,v = ⌧u,v + ⌧v,u R(u, v) = D u,v 2m