Discrete Math Seminar: Cedric Chauve

  • Date: 04/10/2012
  • Time: 14:30
Cedric Chauve

Simon Fraser University


Certificates and spectral approach for the Consecutive-Ones Property



A binary matrix satisfies the Consecutive-Ones Property (C1P) if its
columns can be ordered in such a way that, on each row, the entries 1
are consecutive. Deciding if a matrix satisfies the C1P canbe done in
linear time, and several algorithms exist that can answer this question,
some quite intricated (such as the PQ-tree algorithm of Booth andLueker
In the first part of the talk, I will discuss the notionof non-C1P
certificate: given a matrix M, if an algorithm "answers" that Mis not
C1P, how can we check that this answer is correct ? In other word,can we
provide a structure (certificate) that can be used to validate easily
the answer of the algorithm. The first certificate for the C1P was
proposed in 2004 by McConnell but relies on an auxiliary structure, the
incompatibility graph of M. However, in 1972, Tucker proved that a
matrix is not C1Pif and only if it does contain some submatrix that
belong to 5 well characterized families, which defines a natural notion
of non-C1P certificate. Until recently, it was thought that the result
of Tucker was of little algorithmic interest. Here I will show that,
using an algorithmic technique calledpartition refinement, one can find a
Tucker pattern in a non-C1P matrix inlinear time and space.
In the second part, I will present a result of Atkins, Boman and
Hendrickson that shows that a spectral approach can be usedto decide if a
matrix is C1P. More precisely, let L be the Laplacian of M^t M. If M is
C1P, ordering the columns of M according to the order of entries of an
eigenvector of the second smallest eigenvalue of L makes all entries 1
consectuive in each row. Although computationally inefficient, this
spectral approach raises several questions that I will introduce.
These are works in collaboration with Tamon Stephen, Mehrnoush Malekesmaeili, Maria Tamayo, Ashok Rajaraman.

Other Information: 

For more information please visit SFU Mathematics Department