Discrete Math Seminar: Cedric Chauve

Abstract:

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 (1976)).
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.