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 denned as follows: The Maximum Quasi-biclique Problem: Given a bipartite graph G = (X U Y, E) and a number 0 < 5 < 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 — <5)|yopt| vertices in Y_(opt), any vertex y G Y_(opt) is incident to at least (1 — <5)|Xopt| vertices in X_(opt) and X_(opt) + Y_(opt) is maximized. The problem was proved to be NP-hard [2]. We design a polynomial time approximation scheme to give a quasi-biclique (Xa, Ya) for Xa Q X and Y_a C Y with |X_a| > (1 - ε)X_(opt) and Y_a| > (1 - ε)Y_(opt)| such that any vertex x ∈ X_a is incident to at least (1 — 6 — ε)Y_a| vertices in Y_a and any vertex y ∈ Y_a is incident to at least (1 — 5 — ε)|X_A| vertices in X_a for any e > 0, where X_(opt) and Y_(opt) form the optimal solution.