Hardness results on the gapped consecutive-ones property problem
Motivated by problems in comparative genomics and paleogenomics, we study the computational complexity of the Gapped Consecutive-Ones Property ((k,?) ( k , ? ) -C1P) Problem: given a binary matrix M M and two integers k k and ? ? , decide if the columns of M M can be permuted such that each row contains at most k k blocks of ones and no two neighboring blocks of ones are separated by a gap of more than ? ? zeros. The classical C1P decision problem, which is known to be polynomial-time solvable is equivalent to the (1,0) ( 1 , 0 ) -C1P problem. We extend our earlier results on this problem [C. Chauve, J. Mauch, M. Patterson, On the gapped consecutive-ones property, in: Proceedings of the European Conference on Combinatorics, Graphs Theory and Applications (EuroComb), in: Electronic Notes in Discrete Mathematics, vol. 34, 2009, pp. 121125] to show that for every k?2,??1,(k,?)?(2,1) k ? 2 , ? ? 1 , ( k , ? ) ? ( 2 , 1 ) , the (k,?) ( k , ? ) -C1P Problem is NP-complete, and that for every ??1 ? ? 1 , the (?,?) ( ? , ? ) -C1P Problem is NP-complete. On the positive side, we also show that if k,? k , ? and the maximum degree  of M M are constant, the problem is related to the classical Graph Bandwidth Problem and can be solved in polynomial time using a variant of an algorithm of Saxe [J.B. Saxe, Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time, SIAM Journal on Algebraic and Discrete Methods 1 (4) (1980) 363369].
consecutive-ones property computational complexity graph bandwidth algorithm ancestral genome reconstruction