Matrix sandwich problems Original Research Article

The Π Matrix Sandwich Problem (Π-MSP) is introduced here as follows: Given a {0, 1, *} valued matrix A, where * is interpreted as “do not care”, does there exist a fill-in of the asterisks * with 0s and 1s such that the completed {0, 1} valued matrix M satisfies property Π? We study the computational complexity of this problem for several matrix properties including the Ferrers property, block decompositions and certain forbidden submatrices. Matrix sandwich problems are an important special case of matrix completion problems, the latter being generally defined over the real numbers rather than simply {0, 1}.