Planted Bipartite Graph Detection

Asaf Rotenberg, Wasim Huleihel, Ofer Shayevitz

We consider the task of detecting a hidden bipartite subgraph in a given random graph. This is formulated as a hypothesis testing problem, under the null hypothesis, the graph is a…