The square-root query-complexity conjecture for testing H-minor freeness

From papers

Let HH be a fixed graph. In the bounded-degree graph model, a graph is HH-minor free if it contains no minor isomorphic to HH.

Square-root query-complexity conjecture. For every HH, being HH-minor free can be tested with one-sided error using O~(n)\tilde{O}(\sqrt{n}) queries, where nn is the number of vertices.

The paper notes an Ω(n)\Omega(\sqrt{n}) lower bound for testing HH-minor freeness with one-sided error when HH 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

No solutions have been posted yet.