2017/07/01 by Rani, M R, Subashini, R, Jagalmohanan, Mohith
#Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #G.2.2 #I.1.2
paper · doi:10.48550/arxiv.1707.00106
A binary matrix M has the consecutive ones property (C1P) for rows (resp. columns) if there is a permutation of its columns (resp. rows) that arranges the ones consecutively in all the rows (resp. columns). If M has the C1P for rows and columns, then M is said to have the simultaneous consecutive ones property (SC1P). In this article, we consider the classical complexity and fixed-parameter tractability of (a) Simultaneous Consecutive Ones Submatrix (SC1S) and (b) Simultaneous Consecutive Ones Editing (SC1E) [Oswald et al., Theoretical Comp. Sci. 410(21-23):1986-1992, \hyperref[references]2009] problems. We show that the decision versions of SC1S and SC1E problems are NP-complete. We consider the parameterized versions of SC1S and SC1E problems with d, being the solution size, as the parameter. Given a binary matrix M and a positive integer d, d-SC1S-R, d-SC1S-C, and d-SC1S-RC problems decide whether there exists a set of rows, columns, and rows as well as columns, respectively, of size at most d, whose deletion results in a matrix with the SC1P. The d-SC1P-0E, d-SC1P-1E, and d-SC1P-01E problems decide whether there exists a set of 0-entries, 1-entries, and 0-entries as well as 1-entries, respectively, of size at most d, whose flipping results in a matrix with the \vspace0.095 in SC1P.