Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks Tsuyoshi. Do we know anything of the problem if B is relatively sparse? –  Sudeep Kamath Oct 21 '10 at 18:49
    
@Sudeep: If you really just mean that B is sparse, the problem does not change if B is all-0 (invert all entries of A and B). If you mean that both A and B are sparse, I do not know what happens in that case. –  Tsuyoshi Ito Oct 21 '10 at 23:43
add comment

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.

share|improve this answer
1  
Unless I am mistaken, this IS the (multi+directed) graph isomorphism problem, for padding the matrices with 0s makes them square. This problem is NP-complete, because it contains graph isomorphism as a special case. nauty (cs.sunysb.edu/~algorith/implement/nauty/implement.shtml) can often work very quickly, but unless P != NP, no algorithm can perform well here in the worst case. –  Eric Tressler Oct 21 '10 at 1:26
    
I should also say that, at least for me, nauty was a little bit daunting to get up and running, and I'm not sure it can handle this general situation (graphs with both directed and undirected edges, or if you like, digraphs with some multi-edges). –  Eric Tressler Oct 21 '10 at 1:28
    
In any case, the naive algorithm for graph isomorphism applies here without modification, and it is quite slow. –  Eric Tressler Oct 21 '10 at 1:28
1  
@Eric Tressler: I am afraid that you are confusing the graph isomorphism problem and the subgraph isomorphism problem. The graph isomorphism problem is not known to be NP-complete, and it is not NP-complete unless the polynomial hierarchy collapses. The subgraph isomorphism problem includes the clique problem as a special case and therefore it is NP-complete. Nauty solves the graph isomorphism problem but not the subgraph isomorphism problem. –  Tsuyoshi Ito Oct 21 '10 at 3:10
    
Thank you, Tsuyoshi. I had forgotten the distinction. Your answer reminds me of precisely why the subgraph problem is harder. –  Eric Tressler Oct 21 '10 at 8:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.