BAD'16 Poster

Bristol Algorithms Days 2016
Workshop on Efficient Algorithms and Lower Bounds

2 - 3 February 2016

  •    •    •  

Vacant sets and vacant nets: Critical times for simple and modified random walks

Colin Cooper

The first part of the talk is an introduction to the idea of the vacant set of a discrete random walk. The vacant set of a random walk is the set of vertices of the graph not visited by the walk. Similarly, the vacant net is the set of unvisited edges.

We study the change in size and structure of the graph induced by the vacant set as the walk proceeds. A critical time is a step of the walk before which the graph of the vacant set contains large unexplored connected components, and after which it contains only small unexplored components. For some classes of random graphs we can find a precise critical time.

In the second part of the talk, we compare the critical time on these graphs for three types of random walks (simple, non-backtracking, unexplored edges first). In order to break the graph up into small unexplored components as quickly as possible, the walk with the earliest critical time is best.


  The University of Bristol   EPSRC