Planted Bipartite Graph Detection

02/07/2023
by   Asaf Rotenberg, et al.
0

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 k_𝖱× k_𝖫 bipartite 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 𝖰 edge queries. For this problem, we derive upper and lower bounds in both the dense and sparse regimes.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset