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 delta, decide if the columns of M can be ordered such that each row contains at most k blocks of 1's, and no two neighboring blocks of 1's are separated by a gap of more than delta 0's. This problem was introduced by Chauve et al. (2009b). 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 (Manuch et al., 2011; Goldberg et al., 1995). In this article, we study the Gapped C1P Problem with a third parameter d, namely the bound on the maximum number of 1's in any row of M, or the bound on the maximum degree of M. This is motivated by the reconstruction of ancestral genomes (Ma et al., 2006; Chauve and Tannier, 2008), where, in binary matrices obtained from the experiments of Chauve and Tannier (2008), we have observed that the majority of the rows have low degree, while each high degree row contains many rows of low degree. The (d, k, delta)-C1P Problem has been shown to be polynomial-time solvable when all three parameters are fixed (Chauve et al., 2009b). Since fixing d also fixes k (k <= d), the only case left to consider is the case when delta 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.