Permuting matrices to avoid forbidden submatrices Original Research Article

This paper attaches a frame to a natural class of combinatorial problems and points out that this class includes many important special cases. A matrix M is said to avoid a set F of matrices if M does not contain any element of F as (ordered) submatrix. For F a fixed set of matrices, we consider the problem of deciding whether the rows and columns of a matrix can be permuted in such a way that the resulting matrix M avoids all matrices in F. We survey several known and new results on the algorithmic complexity of this problem, mostly dealing with (0,1)-matrices. Among others, we will prove that the problem is polynomial time solvable for many sets F containing a single, small matrix and we will exhibit some example sets F for which the problem is NP-complete.