Skip to main content

Research Repository

Advanced Search

Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time

Berenbrink, P.; Cooper, C.; Friedetzky, T.

Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time Thumbnail


Authors

P. Berenbrink

C. Cooper



Abstract

Let G = (V,E) be a connected graph with |V | = n vertices. A simple random walk on the vertex set of G is a process, which at each step moves from its current vertex position to a neighbouring vertex chosen uniformly at random. We consider a modified walk which, whenever possible, chooses an unvisited edge for the next transition; and makes a simple random walk otherwise. We call such a walk an edge-process (or E -process). The rule used to choose among unvisited edges at any step has no effect on our analysis. One possible method is to choose an unvisited edge uniformly at random, but we impose no such restriction. For the class of connected even degree graphs of constant maximum degree, we bound the vertex cover time of the E -process in terms of the edge expansion rate of the graph G, as measured by eigenvalue gap 1 -λmax of the transition matrix of a simple random walk on G. A vertex v is ℓ -good, if any even degree subgraph containing all edges incident with v contains at least ℓ vertices. A graph G is ℓ -good, if every vertex has the ℓ -good property. Let G be an even degree ℓ -good expander of bounded maximum degree. Any E -process on G has vertex cover time equation image This is to be compared with the Ω(nlog n) lower bound on the cover time of any connected graph by a weighted random walk. Our result is independent of the rule used to select the order of the unvisited edges, which could, for example, be chosen on-line by an adversary. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2013 As no walk based process can cover an n vertex graph in less than n - 1 steps, the cover time of the E -process is of optimal order when ℓ =Θ (log n). With high probability random r -regular graphs, r ≥ 4 even, have ℓ =Ω (log n). Thus the vertex cover time of the E -process on such graphs is Θ(n).

Citation

Berenbrink, P., Cooper, C., & Friedetzky, T. (2015). Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time. Random Structures and Algorithms, 46(1), 36-54. https://doi.org/10.1002/rsa.20504

Journal Article Type Article
Acceptance Date Apr 8, 2013
Online Publication Date Jun 27, 2013
Publication Date Jan 1, 2015
Deposit Date Apr 23, 2013
Publicly Available Date Mar 29, 2024
Journal Random Structures and Algorithms
Print ISSN 1042-9832
Electronic ISSN 1098-2418
Publisher Wiley
Peer Reviewed Peer Reviewed
Volume 46
Issue 1
Pages 36-54
DOI https://doi.org/10.1002/rsa.20504
Keywords Random walk, Cover time, Random graph, Rotor-router model.
Related Public URLs https://arxiv.org/abs/1204.1939

Files

Accepted Journal Article (345 Kb)
PDF

Copyright Statement
This is the accepted version of the following article: Berenbrink, P., Cooper, C. and Friedetzky, T. (2015), Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time. Random Structures & Algorithms, 46(1): 36-54, which has been published in final form at http://dx.doi.org/10.1002/rsa.20504. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.





You might also like



Downloadable Citations