The square-root query-complexity conjecture for testing H-minor freeness
Let be a fixed graph. In the bounded-degree graph model, a graph is -minor free if it contains no minor isomorphic to .
Square-root query-complexity conjecture. For every , being -minor free can be tested with one-sided error using queries, where is the number of vertices.
The paper notes an lower bound for testing -minor freeness with one-sided error when is not a tree, so the conjecture asserts that this lower bound is tight up to polylogarithmic factors. The broader status of the conjecture is not specified in the source.
References
- Itai Benjamini, Oded Schramm and Asaf Shapira, “Every Minor-Closed Property of Sparse Graphs is Testable”, arXiv:0801.2797 (2008).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.