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:

  1. 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.

  2. 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.

  3. 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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.