The square-root query-complexity conjecture for testing H-minor freeness
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Itai Benjamini, Oded Schramm and Asaf Shapira, “Every Minor-Closed Property of Sparse Graphs is Testable”, arXiv:0801.2797 (2008).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.