On efficient graph covers and steered random walks

Abstract

We prove that the vertices of any $n$-vertex graph can be partitioned into pieces of radius $r = O(\log n)$ such that the sum of the sizes of their closed neighborhoods is at most $4n$. This answers a recent question of Bukh and Dubroff and directly yields an improvement to their upper bound on the optimal cover time of the $\epsilon$-steered random walk. We also demonstrate that our bound on $r$ is best possible up to a constant factor for graphs with strong vertex expansion.