2010/07/23 by Czumaj, Artur, Goldreich, Oded, Ron, Dana +3 · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1007.4230
We present sublinear-time (randomized) algorithms for finding simple cycles of length at least k≥ 3 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 (i.e., Ω(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 \tildeO(√(N)), where N denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors. The foregoing results are the outcome of our study of the complexity of \em one-sided error property testing algorithms in the bounded-degree graphs model. For example, we show that cycle-freeness of N-vertex graphs can be tested with one-sided error within time complexity \tildeO(\poly(1/\e)⋅√(N)). This matches the known Ω(√(N)) query lower bound, and contrasts with the fact that any minor-free property admits a \em two-sided error tester of query complexity that only depends on the proximity parameter \e. For any constant k≥3, we extend this result to testing whether the input graph has a simple cycle of length at least k. On the other hand, for any fixed tree T, we show that T-minor-freeness has a one-sided error tester of query complexity that only depends on the proximity parameter \e. Our algorithm for finding cycles in bounded-degree graphs extends to general graphs, where distances are measured with respect to the actual number of edges. Such an extension is not possible with respect to finding tree-minors in o(√(N)) complexity.