Faster and simpler minimal conflicting set identification (extended abstract)

DOI10.1007/978-3-642-31265-6_4zbMATH Open1358.68145arXiv1201.5513OpenAlexW1617356293MaRDI QIDQ2904477FDOQ2904477

Authors: Aïda Ouangraoua, Mathieu Raffinot 

Publication date: 14 August 2012

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Abstract: Let C be a finite set of N elements and R = r_1,r_2,..., r_m a family of M subsets of C. A subset X of R verifies the Consecutive Ones Property (C1P) if there exists a permutation P of C such that each r_i in X is an interval of P. A Minimal Conflicting Set (MCS) S is a subset of R that does not verify the C1P, but such that any of its proper subsets does. In this paper, we present a new simpler and faster algorithm to decide if a given element r in R belongs to at least one MCS. Our algorithm runs in O(N^2M^2 + NM^7), largely improving the current O(M^6N^5 (M+N)^2 log(M+N)) fastest algorithm of [Blin {em et al}, CSR 2011]. The new algorithm is based on an alternative approach considering minimal forbidden induced subgraphs of interval graphs instead of Tucker matrices.

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

Recommendations

• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction
• A faster algorithm for finding minimum Tucker submatrices
• A faster algorithm for finding minimum Tucker submatrices
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Boolean and Hadamard matrices (15B34) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (5)

• A faster algorithm for finding minimum Tucker submatrices
• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• NP-completeness of small conflict set generation for congruence closure
• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
• Algorithms for Computing Minimal Conflicts

This page was built for publication: Faster and simpler minimal conflicting set identification (extended abstract)

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