Near optimal solutions for maximum quasi-bicliques

The maximum quasi-biclique problem has been proposed for finding interacting protein group pairs from large protein-protein interaction (PPI) networks. The problem is defined as follows: THE MAXIMUM QUASI-BICLIQUE PROBLEM: Given a bipartite graph G=(X ∪ Y, E) and a number 0 < δ ≤ 0.5, find a subset X_opt of X and a subset Y_opt of Y such that any vertex x ∈ X_opt is incident to at least (1-δ)|Y_opt| vertices in Y_opt, any vertex y ∈ Y_opt is incident to at least (1-δ)|X_opt |vertices in X_opt and |X_opt |+|Y_opt |is maximized. The problem was proved to be NP-hard. We design a polynomial time approximation scheme to give a quasi-biclique X′ ⊆ X and Y′ ⊆ Y with |X′|+|Y′| ≥ (1-ε) (|X_opt |+|Y_opt |) such that any vertex x ∈ X′ is incident to at least (1-δ-ε)|Y′| vertices in Y′ and any vertex y ∈ Y′ is incident to at least (1-δ-ε)|X′| vertices in X′ for any ε > 0, where X_opt and Y_opt form the optimal solution.