Obtaining Matrices with the Consecutive Ones Property by Row Deletions

A binary matrix M 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 d-COS-R (Consecutive Ones Submatrix by Row deletions) problem [9]: Given a matrix M and a positive integer d, decide whether there exists a set of at most d rows of M 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 d-COS-R is fixed-parameter tractable and has the current best run-time of O∗(10d), which is associated with the Interval Deletion problem. We also introduce a closely related optimization problem called Min-ICPSA: For a finite sized universe U the input consists of a family of n pairs of sets S = {(Ai, Bi) | Ai, Bi ⊆ u, 1 ≤ i ≤ n}; the aim is to find a minimum number of pairs of sets to discard from S such that for each one of the remaining pairs, say (Ak, BAk), |A|k= |B|k and for any two of the remaining pairs, indexed by 1 ≤ j ≠ k ≤ n, |Aj ∩ Ak| = |Bj ∩ Bk|. 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 |A|.k = 2, 1 ≤ k ≤ n.