On certificates that a matrix does not have the Consecutive Ones Property

Resource type
Thesis type
(Thesis) M.Sc.
Date created
A binary matrix has the consecutive ones property (C1P) if there exists a permutation of its columns which makes the 1s consecutive in every row. The C1P has many applications which range from computational biology to optimization. We give an overview of the C1P and its connections to other related problems. The main contribution of this thesis is about certificates of non-C1Pness. The notion of incompatibility graph of a binary matrix was introduced in [McConnell, SODA 2004] where it is shown that odd cycles of this graph provide a certificate for a non-C1P matrix. A bound of k + 2 was claimed for the smallest odd cycle of a non-C1P matrix with k columns. We show that this result can be obtained directly via Tucker patterns, and that the correct bound is k + 2 when k is even, but k + 3 when k is odd. Furthermore we empirically study the minimal conflicting set certificate on synthetic data.
Copyright statement
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Stephen, Tamon
Member of collection
Download file Size
etd6905_MMalekesmaeili.pdf 4.4 MB

Views & downloads - as of June 2023

Views: 11
Downloads: 1