  A binary matrix has the Consecutive Ones Property (C1P) if its columns can be
ordered in such a way that all 1s on each row are consecutive. These matrices
are used for DNA physical mapping and ancestral genome reconstruction in
computational biology on the other hand they represents a class of convex
bipartite graphs and are of interest of algorithm graph theory researchers.
Tucker gave a forbidden submartices characterization of matrices that have C1P
property in 1972. Booth and Lucker (1976) gave a first linear time recognition
algorithm for matrices with C1P property and then in 2002, Habib, et al. gave a
simpler linear time recognition algorithm. There has been substantial amount of
works on efficiently finding minimum size forbidden submatrix. Our algorithm is
at least $n$ times faster than the existing algorithm where $n$ is the number
of columns of the input matrix.

Data Structures and Algorithms