Testing Hamiltonicity (and other problems) in Minor-Free Graphs

Reut Levi, Nadav Shoshan

In this paper we provide sub-linear algorithms for several fundamental problems in the setting in which the input graph excludes a fixed minor, i.e., is a minor-free graph. In part…