A note on the consecutive ones submatrix problem. (Q1853060): Difference between revisions

A binary matrix has the Consecutive Ones Property (C1P) for columns if there exists a permutation of its rows that leaves the 1's consecutive in every column. The problem of Consecutive Ones Property for a matrix is a special variant of Consecutive Ones Submatrix problem in which a positive integer \(K\) is given and we want to know if there exists a submatrix \(B\) of \(A\) consisting of \(K\) columns of \(A\) with C1P property. This paper presents an error in the proof of NP-completeness for this problem in the reference cited in text by \textit{M. R. Garey} and \textit{D. S. Johnson} [Computers and Intractability, A Guide to the Theory of NP-Completeness (1979)].