×

The electrical resistance of a graph captures its commute and cover times. (English) Zbl 0905.60049

Summary: View an \(n\)-vertex, \(m\)-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices \(s\) and \(t\) (the expected length of a random walk from \(s\) to \(t\) and back) is precisely characterized by the effective resistance \(R_{st}\) between \(s\) and \(t\): commute time \(=2m R_{st}\). As a corollary, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance \(R\) in the graph to within a factor of \(\log n\): \(mR\leq \text{cover time} \leq O(mR \log n)\). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, we improve known bounds on cover times for high-degree graphs and expanders, and give new proofs of known results for multidimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.

MSC:

60G50 Sums of independent random variables; random walks
68Q99 Theory of computing
Full Text: DOI

References:

[1] D. J. Aldous, On the time taken by random walks on finite groups to visit every state.Z. Wahrsch. Verw. Gebiete 62(3) (1983), 361?374. · Zbl 0488.60011 · doi:10.1007/BF00535260
[2] D. J. Aldous,Reversible Markov chains and random walks on graphs. 1993. Draft, University of California, Berkeley.
[3] R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. W. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems. InProc. 20th Ann. IEEE Symp. Found. Comput. Sci., San Juan, Puerto Rico, 1979, IEEE, 218?223.
[4] N. Alon, Eigenvalues and expanders.Combinatorica 6(2) (1986), 83?96. · Zbl 0661.05053 · doi:10.1007/BF02579166
[5] G. Barnes andU. Feige, Short random walks on graphs.SIAM J. Disc. Math. 9(1) (1996), 19?28. · Zbl 0843.60065 · doi:10.1137/S0895480194264988
[6] A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, andM. Tompa, Two applications of inductive counting for complementation problems.SIAM J. Comput. 18(3) (1989), 559?578. See also18(6): 1283, December 1989. · Zbl 0678.68031 · doi:10.1137/0218038
[7] A. Borodin, W. L. Ruzzo, andM. Tompa, Lower bounds on the length of universal traversal sequences.J. Comput. System Sci. 45(2) (1992), 180?203. · Zbl 0754.68061 · doi:10.1016/0022-0000(92)90046-L
[8] A. Z. Broder andA. R. Karlin, Bounds on the cover time.J. Theoret. Probability 2(1) (1989), 101?120. · Zbl 0681.60063 · doi:10.1007/BF01048273
[9] A. Z. Broder, A. R. Karlin, P. Raghavan, andE. Upfal, Trading space for time in undirecteds-t connectivity.SIAM J. Comput. 23(2) (1994), 324?334. · Zbl 0804.68105 · doi:10.1137/S0097539790190144
[10] A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari, The electrical resistance of a graph captures its commute and cover times. InProc. Twenty-first Ann. ACM Symp. Theor. Comput., Seattle, WA, 1989, 574?586.
[11] J. T. Cox, Coalescing random walks and voter model consensus times on the torus inZd.The Annals of Probability 17(4) (1989), 1333?1366. · Zbl 0685.60100 · doi:10.1214/aop/1176991158
[12] P. G. Doyle, Personal communication, 1988.
[13] P. G. Doyle and J. L. Snell,Random Walks and Electrical Networks. The Mathematical Association of America, 1984. · Zbl 0583.60065
[14] M. Dyer, A. M. Frieze, andR. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies.J. Assoc. Comput. Mach. 38(1) (1991), 1?17. · Zbl 0799.68107 · doi:10.1145/102782.102783
[15] U. Feige, A randomized time-space tradeoff of $$\(\backslash\)tilde O(m\(\backslash\)hat R)$$ for USTCON. InProc. 34th Ann. Symp. Found. Comput. Sci., Palo Alto, CA, 1993, IEEE, 238?246.
[16] J. N. Franklin,Matrix Theory. Prentice-Hall, 1968.
[17] J. Friedman and N. J. Pippenger, Expanding graphs contain all small trees.Combinatorica (1987), 71?76. · Zbl 0624.05028
[18] F. Göbel andA. A. Jagers, Random walks on graphs.Stochastic Processes and their Applications 2 (1974), 311?336. · Zbl 0296.60046 · doi:10.1016/0304-4149(74)90001-5
[19] M. Jerrum andA. Sinclair, Approximating the permanent.SIAM J. Comput. 18(6) (1989), 1149?1178. · Zbl 0723.05107 · doi:10.1137/0218077
[20] J. D. Kahn, N. Linial, N. Nisan, andM. E. Saks, On the cover time of random walks on graphs.J. Theoret. Probability 2(1) (1989), 121?128. · Zbl 0681.60064 · doi:10.1007/BF01048274
[21] H. J. Landau andA. M. Odlyzko, Bounds for eigenvalues of certain stochastic matrices.Linear Algebra and Its Applications 38 (1981), 5?15. · Zbl 0474.05050 · doi:10.1016/0024-3795(81)90003-3
[22] P. Matthews, Covering problems for Brownian motion on spheres.The Annals of Probability 16(1) (1988), 189?199. · Zbl 0638.60014 · doi:10.1214/aop/1176991894
[23] J. C. Maxwell,A Treatise on Electricity and Magnetism. Clarendon, 1918.
[24] D. Peleg andE. Upfal, Constructing disjoint paths on expander graphs.Combinatorica 9(3) (1989), 289?313. · Zbl 0686.68056 · doi:10.1007/BF02125897
[25] S. M. Ross,Introduction to Probability Models. Academic Press, fourth edition, 1989. · Zbl 0676.60002
[26] R. Rubinfeld, The cover time of a regular expander isO(nlogn).Inform. Process. Lett. 35(1) (1990), 49?51. · Zbl 0706.68059 · doi:10.1016/0020-0190(90)90173-U
[27] J. L. Synge, The fundamental theorem of electrical networks.Quarterly of Applied Math. 9 (1951), 113?127. · Zbl 0043.20003
[28] P. Tetali, Random walks and effective resistance of networks.J. Theoret. Probability 4(1) (1991), 101?109. · Zbl 0722.60070 · doi:10.1007/BF01046996
[29] W. Thomson and P. G. Tait,Treatise on Natural Philosophy. Cambridge, 1879. · JFM 15.0767.01
[30] D. I. Zuckerman, On the time to traverse all edges of a graph.Inform. Process. Lett. 38(6) (1991), 335?337. · Zbl 0736.68067 · doi:10.1016/0020-0190(91)90091-U
[31] D. I. Zuckerman, A technique for lower bounding the cover time.SIAM J. Disc. Math. 5(1) (1992), 81?87. · Zbl 0743.60068 · doi:10.1137/0405007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.