On the Gapped Consecutive-Ones Property

Motivated by problems of comparative genomics and paleogenomics, we introduce the Gapped Consecutive-Ones Property Problem (k,δ)-C1P: given a binary matrix M and two integers k and δ, can the columns of M be permuted such that each row contains at most k sequences of 1's and no two consecutive sequences of 1's are separated by a gap of more than δ 0's. The classical C1P problem, which is known to be polynomial, is equivalent to the (1,0)-C1P Problem. We show that the (2,δ)-C1P Problem is NP-complete for δ⩾2. We conjecture that the (k,δ)-C1P Problem is NP-complete for k⩾2, δ⩾1, (k,δ)≠(2,1). We also show that the (k,δ)-C1P Problem can be reduced to a graph bandwidth problem parameterized by a function of k, δ and of the maximum number s of 1's in a row of M, and hence is polytime solvable if all three parameters are constant.