Finding bipartite subgraphs efficiently

Polynomial algorithms are given for the following two problems:
• given a graph with n vertices and m edges, find a complete balanced bipartite subgraph Kq,q with ,
• given a graph with n vertices, find a decomposition of its edges into complete balanced bipartite graphs having altogether O(n2/lnn) vertices.The first algorithm can be modified to have running time linear in m and find a Kq′,q′ with q′=⌊q/5⌋. Previous proofs of the existence of such objects, due to Kővári, Sós and Turán (1954) [10], , Chung, Erdős and Spencer (1983) [5], , Bublitz (1986) [4], and Tuza (1984) [13] were non-constructive.