Locating a submatrix within a matrix - MathOverflow

Locating a submatrix within a matrix

2010-10-20T23:58:18Z

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.

Answer by Nick S for Locating a submatrix within a matrix

2010-10-21T00:17:09Z

This comment is too long to go as a coment, so i have to post as an answer.

When $m=n$ and $p=q$ the problem seems somewhat similar to the graph isomorphism problem. There are three main differences, one being that in the graph isomorphism problem the rows and columns are permutated the same way, the second being that the graph isomorphism problem is asking whenever it is possible to find B and lastly the graph is simple (hence $a_{ii}=0$).

Anyhow, acordingly to Wikipedia there exists "a recursive backtracking procedure for solving the subgraph isomorphism problem", which for fixed $A$ and $B$ is polynomial in the size of $B$. Then there is probably a chance (or maybe not) that you can change that algorithm to suit your needs.

Answer by Tsuyoshi Ito for Locating a submatrix within a matrix

2010-10-21T02:55:25Z

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