0
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Tsuyoshi. Do we know anything of the problem if B is relatively sparse? $\endgroup$
    – Sudeep Kamath
    Oct 21, 2010 at 18:49
  • $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Oct 21, 2010 at 23:43
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Eric Tressler
    Oct 21, 2010 at 1:26
  • $\begingroup$ 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). $\endgroup$
    – Eric Tressler
    Oct 21, 2010 at 1:28
  • $\begingroup$ In any case, the naive algorithm for graph isomorphism applies here without modification, and it is quite slow. $\endgroup$
    – Eric Tressler
    Oct 21, 2010 at 1:28
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Oct 21, 2010 at 3:10
  • $\begingroup$ Thank you, Tsuyoshi. I had forgotten the distinction. Your answer reminds me of precisely why the subgraph problem is harder. $\endgroup$
    – Eric Tressler
    Oct 21, 2010 at 8:08

Your Answer

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

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