The Complexity of the Gapped Consecutive-Ones Property Problem for Matrices of Bounded Maximum Degree

The Gapped Consecutive-Ones Property (C1P) Problem, or the (k, delta)-C1P Problem is: given a binary matrix M and integers k and 5, decide if the columns of M can be ordered such that each row contains at most k blocks of and no two neighboring blocks of are separated by a gap of more than delta 0's. This problem was introduced in [3]. The classical polynomial-time solvable C1P Problem is equivalent to the (1, 0)-C1P problem. It has been shown that for every unbounded or bounded k >= 2 and unbounded or bounded delta >= 1, except when (k, delta) = (2,1), the (k, delta)-C1P Problem is NP-complete [10,6]. In this paper we study the Gapped C1P Problem with a third parameter d, namely the bound on the maximum number of l's in any row of M or the bound on the maximum degree of M. This is motivated by problems in comparative genomics and paleogenomics, where the genome data is often sparse [4]. The (d, k, delta)-C1P Problem has been shown to be polynomial-time solvable when all three parameters are fixed [3]. Since fixing d also fixes k (k <= d), the only case left to consider is the case when (5 is unbounded, or the (d, k, infinity)-C1P Problem. Here we show that for every d > k >= 2, the (d, k, infinity)-C1P Problem is NP-complete.