A note on the Consecutive Ones Submatrix problem

✍ Scribed by Mohammad Taghi Hajiaghayi; Yashar Ganjali

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 53 KB
• Volume: 83
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00325-8

✦ Synopsis

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 Garey and Johnson [Computers and Intractability, A Guide to the Theory of NP- Completeness, 1979].