Near optimal solutions for maximum quasi-bicliques

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)481-497
Journal / PublicationJournal of Combinatorial Optimization
Issue number3
Online published16 Mar 2011
Publication statusPublished - Apr 2013


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=(Y, E) and a number 0 < δ ≤ 0.5, find a subset Xopt of X and a subset Yopt of Y such that any vertex Xopt is incident to at least (1-δ)|Yopt| vertices in Yopt, any vertex yYopt is incident to at least (1-δ)|Xopt |vertices in Xopt and |Xopt |+|Yopt |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-ε) (|Xopt |+|Yopt |) such that any vertex xX′ is incident to at least (1-δ-ε)|Y′| vertices in Y′ and any vertex ∈ Y′ is incident to at least (1-δ-ε)|X′| vertices in X′ for any ε > 0, where Xopt and Yopt form the optimal solution.

Research Area(s)

  • Approximation algorithm, Interacting protein group pairs, Protein interaction sites, Protein-protein interaction networks, Quasi-bicliques