Given an $m\times n$ 0-1 matrix A, I am interested in an efficient algorithm to locate all copies of a given $p\times q$ 0-1 submatrix B within it, where a permutation of rows and columns is allowed, i.e. find all collections of row indices $r\_1, r\_2,\ldots, r\_p$ and column indices $c\_1, c\_2,\ldots, c\_q$ (with $r\_i$'s and $c\_j$'s not necessarily in increasing order) so that A restricted to those rows and columns in that particular order yields B.


Any references will be useful.


Thanks.



Locating a submatrix within a matrix
Note that the problem of deciding whether there exist such row indices and column indices is already NP-complete. This is because the case where *B* is a square matrix entirely consisting of 1s is identical to the Balanced Complete Bipartite Subgraph problem, which is known to be NP-complete [Joh87].


[Joh87] David S. Johnson. The NP-completeness column: An ongoing guide. *Journal of Algorithms*, 8(3):438–448, Sept. 1987. <http://dx.doi.org/10.1016/0196-6774(87)90021-6>


