Generalizations of the Consecutive Ones Property and Related NP-Complete Problems¹

Article type: Research Article

Authors: Lipski Jr., Witold

Affiliations: Polish Academy of Sciences

Note: [1] Part of this work was done while the author was visiting the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign.

Abstract: A(O,1)-matrix A is said to have the consecutive ones property if its rows can be permuted so that the 1’s appear consecutively in each column. We present four NP-complete problems connected with some generalizations of this notion. These problems concern decomposing the columns of a matrix into two subsets having the consecutive ones property, decomposing the rows into three subsets having the consecutive ones property, finding a subset of rows of maximal size having the consecutive ones property, and finding a permutation of the rows such that the 1’s in any column are contained in a set of k consecutive rows, for a fixed “buffer size” k.

Keywords: Computational complexity, NP-complete problems, matrices with the consecutive ones property, linear families of sets, file organization, consecutive retrieval property, storage space minimization

DOI: 10.3233/FI-1983-6104

Journal: Fundamenta Informaticae, vol. 6, no. 1, pp. 53-69, 1983