Avoiding Forbidden Submatrices by Row Deletions

摘要

We initiate a systematic study of the Row Deletion(B) problem on matrices: For a fixed "forbidden submatrix" B, the question is, given an input matrix A (both A and B have entries chosen from a finite-size alphabet), to remove a minimum number of rows such that A has no submatrix which is equivalent to a row or column permutation of B. An application of this question can be found, e.g., in the construction of perfect phylogenies. Establishing a strong connection to variants of the NP-complete Hitting Set problem, we show that for most matrices B Row Deletion(S) is NP-complete. On the positive side, the relation with Hitting Set problems yields constant-factor approximation algorithms and fixed-parameter tractability results.