Locating a submatrix within a matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T06:37:28Z http://mathoverflow.net/feeds/question/42969 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42969/locating-a-submatrix-within-a-matrix Locating a submatrix within a matrix Sudeep Kamath 2010-10-20T23:58:18Z 2010-10-21T02:55:25Z <p>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.</p> <p>Any references will be useful.</p> <p>Thanks.</p> http://mathoverflow.net/questions/42969/locating-a-submatrix-within-a-matrix/42974#42974 Answer by Nick S for Locating a submatrix within a matrix Nick S 2010-10-21T00:17:09Z 2010-10-21T00:17:09Z <p>This comment is too long to go as a coment, so i have to post as an answer.</p> <p>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$).</p> <p>Anyhow, acordingly to <a href="http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem" rel="nofollow">Wikipedia</a> 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.</p> http://mathoverflow.net/questions/42969/locating-a-submatrix-within-a-matrix/42993#42993 Answer by Tsuyoshi Ito for Locating a submatrix within a matrix Tsuyoshi Ito 2010-10-21T02:55:25Z 2010-10-21T02:55:25Z <p>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 <i>B</i> 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].</p> <p>[Joh87] David S. Johnson. The NP-completeness column: An ongoing guide. <em>Journal of Algorithms</em>, 8(3):438–448, Sept. 1987. <a href="http://dx.doi.org/10.1016/0196-6774(87)90021-6" rel="nofollow">http://dx.doi.org/10.1016/0196-6774(87)90021-6</a></p>