N S Narayanaswamy

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.

We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1, ..., n} to each of the subsets, does there exist a bijection f : S → {1, ..., n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment. © 2009 Elsevier B.V. All rights reserved.

Given a set system F ⊆ (2U\∅) of a finite set U of cardinality n and a tree T of size n, does there exist at least one bijection φ : U → V (T) such that for each S ∈ F, the set {φ(x) | x ∈ S} is the vertex set of a path in T? Our main result is that the existence of such a bijection from U to V (T) is equivalent to the existence of a function l from F to the set of all paths in T such that for any three, not necessarily distinct, S1, S2, S3 ∈ F, |S1 ∩ S2 ∩ S3| = |l (S1) ∩ l (S2) ∩ l (S3)|. l is referred to as a tree path labeling of F.