2013/03/07 by N. S. Narayanaswamy, Narayanaswamy, N. S., R. Subashini +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1303.1643
openalex publication_date 2013/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A binary matrix M has the Consecutive Ones Property (COP) if there exists a permutation of columns that arranges the ones consecutively in all the rows. Given a matrix, the d-COS-R problem is to determine if there exists a set of at most d rows whose deletion results in a matrix with COP. We consider the parameterized complexity of this problem with respect to the number d of rows to be deleted as the parameter. The closely related Interval Deletion problem has recently shown to be FPT [Y. Cao and D. Marx, Interval Deletion is Fixed-Parameter Tractable, arXiv:1211.5933 [cs.DS],2012]. In this work, we describe a recursive depth-bounded search tree algorithm in which the problems at the leaf-level are solved as instances of Interval Deletion. The running time of the algorithm is dominated by the running time of Interval Deletion, and therefore we show that d-COS-R is fixed-parameter tractable and has a run-time of O^*(10d).