Finding bipartite subgraphs efficiently

D. Mubayi, G. Turan

Polynomial algorithms are given for the following two problems: given a graph with $n$ vertices and $m$ edges, where $m\ge 3n^{3/2}$, find a complete balanced bipartite subgraph…