THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS

摘要

We initiate a systematic study of the ROW DELETION(B) problem on matrices: Given an input matrix A and a fixed "forbidden submatrix" B, the task is to remove a minimum number of rows from A such that no row or column permutation of B occurs as a submatrix in the resulting matrix. An application of this problem can be found, for instance, in the construction of perfect phylogenies. Establishing a strong connection to variants of the NP-complete HITTINGS ET problem, we describe and analyze structural properties of B that make ROWD ELETION(B) NP -complete. On the positive side, the close relation with HITTINGS ET problems yields constant-factor polynomial-time approximation algorithms and fixed-parameter tractability results.