Finding cycles and trees in sublinear time (Q2925521)

This paper presents sublinear-time (randomized) algorithms for finding simple cycles of length at least \(k\geq 3\) and tree-minors in bounded-degree graphs. The complexity of these algorithms is related to the distance of the graph from being \(C_k\)-minor-free (resp., free from having the corresponding tree-minor). In particular, if the graph is far (i.e., \(\Omega(1)\)-far) from being cycle-free, i.e. if one has to delete a constant fraction of edges to make it cycle-free, then the algorithm finds a cycle of polylogarithmic length in time \(\tilde O(\sqrt{N})\), where \(N\) denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors.