  The cover-time problem, i.e., time to visit every site in a system, is one of
the key issues of random walks with wide applications in natural, social, and
engineered systems. Addressing the full distribution of cover times for random
walk on complex structures has been a long-standing challenge and has attracted
persistent efforts. Yet, the known results are essentially limited to
homogeneous systems, where different sites are on an equal footing and have
identical or close mean first-passage times, such as random walks on a torus.
In contrast, realistic random walks are prevailingly heterogeneous with
diversified mean first-passage times. Does a universal distribution still
exist? Here, by considering the most general situations, we uncover a
generalized rescaling relation for the cover time, exploiting the diversified
mean first-passage times that have not been accounted for before. This allows
us to concretely establish a universal distribution of the rescaled cover times
for heterogeneous random walks, which turns out to be the Gumbel universality
class that is ubiquitous for a large family of extreme value statistics. Our
analysis is based on the transfer matrix framework, which is generic that
besides heterogeneity, it is also robust against biased protocols, directed
links, and self-connecting loops. The finding is corroborated with extensive
numerical simulations of diverse heterogeneous non-compact random walks on both
model and realistic topological structures. Our new technical ingredient may be
exploited for other extreme value or ergodicity problems with nonidentical
distributions.
