Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that all rows sum to $\ge p$, all columns sum to $\ge q$, and the number of columns is $\le k$. Equivalently, given a bipartite graph $G = \langle U, W, E \rangle$, find a subgraph $G’ = \langle U’, W’, E’ \rangle$ where the minimum degree is $p$ for all $u \in U’$ and $q$ for all $w \in W’$, where $|W’| \leq k$, and where $|U’|$ is as large as possible, if any such subgraph exists.
Here's what I know so far:
A naïve algorithm that alternately deletes invalid rows and columns finds a solution in time $O(mn(m+n))$, if the row maximizing solution fortuitously has number of columns $\le k$. (A tighter bound accounting for sparsity could be given.) Its I/O behavior is not good though.
With constraining $k$, the problem is an instance of (an optimization version of) Lov\'{a}sz's GENERAL FACTOR PROBLEM. GFP asks whether a graph has a subgraph such that each vertex has a degree that falls in a specified set. I can cast my problem as GFP by defining a bipartite graph $\langle \{U \cup y \}, \{W \cup x \}, E^{+} \rangle$ by adding a vertex $x$ with an edge to all vertices in $U$, and vertex $y$ with an edge to all vertices in $W$. We require all vertices in $U$ to have degree in the set $\{0,p,p+1,…, n\}$, all vertices in $W$ to have degree in the set $\{0, q,q+1,…, m\}$, and vertex $y$ to have degree in the set $\{1,…, k\}$. We define vertex $x$ to have degree $j$, and do binary search on $j$ with a solver (that finds a solution, not just yes/no) for GENERAL FACTOR PROBLEM as a subroutine. Unfortunately, GFP is NP-complete when there are gaps greater than 1 in the degree set (as the 0's for dropping nodes introduce). And while there's a lot of theoretical work on GFP, I haven't found any heuristic algorithms appropriate for large data sets.
There are several definitions of a quasi-biclique and heuristic algorithms for finding them in large graphs (e.g. social network or genomics data). Unfortunately, the ones I have found either constrain degree on nodes in only one side of the bipartite graph, or use symmetric criteria that effectively allow only certain combinations of $p$ and $q$ to be used. Abello, Resende, and Sudarsky give a semi-external algorithm for large graphs, but use a definition of quasi-biclique based on edge density that doesn't match my needs at all.
Any pointers to semi-external or external memory algorithms for my problem, or suggestions of other ways to think about it?
