Tight query complexity bounds for learning graph partitions

Xizhi Liu, Sayan Mukherjee

Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not. We prove that for $n\g…