The maximum edge biclique problem is NP-complete

By René Peeters. Discrete Applied Mathematics, 2003

433 citations recorded by the source corpus.

Abstract We prove that the maximum edge biclique problem in bipartite graphs is NP-complete.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

CopyCatch: stopping group attacks by spotting lockstep behavior in social networks (2013, background): “As shown in [22], finding bipartite cores in a graph is NP-hard.”
Community detection in graphs (2009, background): “Finding all Nc bicliques of a graph is an NP-complete problem (Peeters, 2003), mostly because the number of bicliques tends to grow exponentially with the size of the graph.”
Low-Rank Matrix Approximation with Weights or Missing Data Is NP-Hard (2010, neutral): “In fact, it is equivalent to the implication Given K , does G b contain a biclique with at least K edges? has been shown to be NP-complete [23] in the usual Turing machine model [9], which is our framework in this paper.”
On the Geometric Interpretation of the Nonnegative Rank (2010, background): “Note however that finding the biclique with the maximum numberof edges is a combinatorialNP-hardoptimizationproblem[40].”
The role mining problem: finding a minimal descriptive set of roles (2007, background): “, [8] and [17]) – though most concentrate on finding one biclique from a bipartite or general graph.”
Biclustering algorithms for biological data analysis: a survey (2004, neutral): “Finding a maximum size bicluster is therefore equivalent to finding the maximum edge biclique in a bipartite graph, a problem known to be NP-complete [20].”