THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
Sebastian Wernicke, Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier · International Journal of Foundations of Computer Science · 2006
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 HITTING SET problem, we describe and analyze structural properties of B that make ROW DELETION(B)NP-complete. On the positive side, the close relation with HITTING SET problems yields constant-factor polynomial-time approximation algorithms and fixed-parameter tractability results.