2020/06/30 by John Haslegrave, Thomas Sauerwald, John Sylvester · 3 citations
Computer Science · Mathematics · #Combinatorics #Complexity and Algorithms in Graphs #Conjecture #Cover (algebra) #Discrete mathematics #Generality #Graph #Markov Chains and Monte Carlo Methods #Mathematics #Optimization and Search Problems #Random walk #Statistics #Vertex (graph theory) #acm:05C81 #acm:60J10 #acm:68Q17 #acm:68R10 #cs.DM #math.CO #math.PR #msc:05C81 #msc:60J10 #msc:68Q17 #msc:68R10
paper · pdf · open access · doi:10.1145/3498848
published in ACM Transactions on Algorithms 18(2), 1-30 (Association for Computing Machinery) · 32 pages, 5 figures. Theorems 3.4 and 4.3 have been slightly strengthened in version 2. Some results from this paper appeared in The 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of LIPIcs, pages 76:1-76:19
arxiv created 2021/08/04 · openalex publication_date 2022/03/15 · arxiv updated 2022/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study the biased random walk where at each step of a random walk a "controller" can, with a certain small probability, move the walk to an arbitrary neighbour. This model was introduced by Azar et al. [STOC'1992]; we extend their work to the time dependent setting and consider cover times of this walk. We obtain new bounds on the cover and hitting times. Azar et al. conjectured that the controller can increase the stationary probability of a vertex from p to p1-ε; while this conjecture is not true in full generality, we propose a best-possible amended version of this conjecture and confirm it for a broad class of graphs. We also consider the problem of computing an optimal strategy for the controller to minimise the cover time and show that for directed graphs determining the cover time is PSPACE-complete.