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(B) is NP-complete. On the positive side, the relation with hitting set problems yields constant-factor approximation algorithms and fixed-parameter tractability results.
展开▼
