Obtaining Matrices with the Consecutive Ones Property by Row Deletions

A binary matrix has the Consecutive Ones Property (COP) if there exists a permutation of columns that arranges the ones consecutively in all the rows. We consider the parameterized complexity of -COS-R (Consecutive Ones Submatrix by Row deletions) problem [9]: Given a matrix and a positive integer , decide whether there exists a set of at most rows of whose deletion results in a matrix with the COP. The closely related Interval Deletion problem has recently been shown to be FPT [6]. We show that -COS-R is fixed-parameter tractable and has the current best run-time of , which is associated with the Interval Deletion problem. We also introduce a closely related optimization problem called Min-ICPSA: For a finite sized universe the input consists of a family of pairs of sets ; the aim is to find a minimum number of pairs of sets to discard from such that for each one of the remaining pairs, say , and for any two of the remaining pairs, indexed by , . We show that Min-ICPSA is computationally equivalent to the Vertex Cover problem. We also show that it is at least as hard as the Hamilton Path problem in undirected graphs, even when each vertical bar A(k)vertical bar = 2, 1 <= k <= n.