Finding cycles and trees in sublinear time
We present sublinear-time (randomized) algorithms for finding simple cycles of length at least and tree-minors in bounded-degree graphs. The complexity of these algorithms is related to the distance of the graph from being Ck-minor free (resp., free from having the corresponding tree-minor). In particular, if the graph is -far from being cycle-free (i.e., a constant fraction of the edges must be deleted to make the graph cycle-free), then the algorithm finds a cycle of polylogarithmic length in time , where N denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors.
bounded-degree graphs sublinear-time algorithms property testing one-sided versus two-sided error probability