2012/04/09 by Petra Berenbrink, Berenbrink, Petra, Colin Cooper +3
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1204.1939
We consider a modified random walk which uses unvisited edges whenever\npossible, and makes a simple random walk otherwise. We call such a walk an\nedge-process. We assume there is a rule A, which tells the walk which unvisited\nedge to use whenever there is a choice. In the simplest case, A is a uniform\nrandom choice over unvisited edges incident with the current walk position.\nHowever we do not exclude arbitrary choices of rule A. For example, the rule\ncould be determined on-line by an adversary, or could vary from vertex to\nvertex.\n For even degree expander graphs, of bounded maximum degree, we have the\nfollowing result. Let G be an n vertex even degree expander graph, for which\nevery vertex is in at least one vertex induced cycle of length L. Any\nedge-process on G has cover time (n+ (n log n)/L). This result is independent\nof the rule A used to select the order of the unvisited edges, which can be\nchosen on-line by an adversary.\n As an example, With high probability, random r-regular graphs, (r at least 4,\neven), are expanders for which L = Omega(log n). Thus, for almost all such\ngraphs, the vertex cover time of the edge-process is Theta(n). This improves\nthe vertex cover time of such graphs by a factor of log n, compared to the\nOmega(n log n) cover time of any weighted random walk.\n