Detecting a Planted Bipartite Graph
Asaf Rotenberg, Wasim Huleihel, Ofer Shayevitz · 2023
We consider the task of detecting a hidden bipartite subgraph in a given random graph. Specifically, under the null hypothesis, the graph is a realization of an Erdős-Rényi random graph over n vertices with edge density q. Under the alternative, there exists a planted kR× kLbipartite subgraph with edge density p > q. We derive asymptotically tight upper and lower bounds for this detection problem in both the dense regime, where q, p = Θ(1), and the sparse regime where q, p = Θ(n−α), α ∈ (0, 2]. Moreover, we consider a variant of the above problem, where one can only observe a relatively small part of the graph, by using at most Q edge queries. For this problem, we derive upper and lower bounds in both the dense and sparse regimes, and observe a gap between them.