License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.107
URN: urn:nbn:de:0030-drops-141764
Go to the corresponding LIPIcs Volume Portal

Rivera, Nicolás ; Sauerwald, Thomas ; Sylvester, John

Multiple Random Walks on Graphs: Mixing Few to Cover Many

LIPIcs-ICALP-2021-107.pdf (0.8 MB)


Random walks on graphs are an essential primitive for many randomised algorithms and stochastic processes. It is natural to ask how much can be gained by running k multiple random walks independently and in parallel. Although the cover time of multiple walks has been investigated for many natural networks, the problem of finding a general characterisation of multiple cover times for worst-case start vertices (posed by Alon, Avin, Koucký, Kozma, Lotker, and Tuttle in 2008) remains an open problem.
First, we improve and tighten various bounds on the stationary cover time when k random walks start from vertices sampled from the stationary distribution. For example, we prove an unconditional lower bound of Ω((n/k) log n) on the stationary cover time, holding for any n-vertex graph G and any 1 ≤ k = o(nlog n). Secondly, we establish the stationary cover times of multiple walks on several fundamental networks up to constant factors. Thirdly, we present a framework characterising worst-case cover times in terms of stationary cover times and a novel, relaxed notion of mixing time for multiple walks called the partial mixing time. Roughly speaking, the partial mixing time only requires a specific portion of all random walks to be mixed. Using these new concepts, we can establish (or recover) the worst-case cover times for many networks including expanders, preferential attachment graphs, grids, binary trees and hypercubes.

BibTeX - Entry

  author =	{Rivera, Nicol\'{a}s and Sauerwald, Thomas and Sylvester, John},
  title =	{{Multiple Random Walks on Graphs: Mixing Few to Cover Many}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{107:1--107:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-141764},
  doi =		{10.4230/LIPIcs.ICALP.2021.107},
  annote =	{Keywords: Multiple Random walks, Markov Chains, Random Walks, Cover Time}

Keywords: Multiple Random walks, Markov Chains, Random Walks, Cover Time
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI