Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results

DOI10.1016/J.TCS.2019.05.043MaRDI QIDQ2297848zbMATH OpenOpenAlexWikidataFDO

Authors Rani M. R, Subashini R, Mohith Jagalmohanan

Publication date 20 February 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.00106

zbMATH Keywords

consecutive-ones property (C1P)fixed-parameter tractable (FPT)parameterized complexitysimultaneous consecutive-ones property (SC1P)

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Combinatorics in computer science (68R05)

Abstract: 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 vspace{0.095 in} $SC1P$.

Recommendations

• Classical complexity and fixed-parameter tractability of simultaneous consecutive ones submatrix \& editing problems
• FPT algorithms for consecutive ones submatrix problems
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• The simultaneous consecutive ones problem
• Obtaining matrices with the consecutive ones property by row deletions

Cites work

• A certifying algorithm for the consecutive-ones property
• A faster algorithm for finding minimum Tucker submatrices
• A faster algorithm for finding minimum Tucker submatrices
• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• A Simple Test for the Consecutive Ones Property
• A structure theorem for the consecutive 1's property
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Chordal editing is fixed-parameter tractable
• Complexity classification of some edge modification problems
• Computing the Minimum Fill-In is NP-Complete
• Consecutive ones property testing: cut or swap
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Faster and simpler minimal conflicting set identification (extended abstract)
• Fundamentals of parameterized complexity
• Hardness results on the gapped consecutive-ones property problem
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2003406 (Why is no real title available?)
• Incidence matrices and interval graphs
• Interval graphs and interval orders
• Linear recognition of almost interval graphs
• Node-and edge-deletion NP-complete problems
• Node-Deletion Problems on Bipartite Graphs
• Obtaining matrices with the consecutive ones property by row deletions
• On the consecutive ones property
• On the gapped consecutive-ones property
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• PC trees and circular-ones arrangements.
• Proper interval vertex deletion
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The simultaneous consecutive ones problem
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs

Cited in

(9)

• A note on the consecutive ones submatrix problem.
• Obtaining matrices with the consecutive ones property by row deletions
• FPT algorithms for consecutive ones submatrix problems
• Eliminating switching components in binary matrices by 0-1 flips and column permutations
• THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
• scientific article; zbMATH DE number 2104735 (Why is no real title available?)
• Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems
• Classical complexity and fixed-parameter tractability of simultaneous consecutive ones submatrix \& editing problems
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems

This page was built for publication: Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297848)