A certifying algorithm for the consecutive-ones property

Abstract

We give a forbidden substructure characterization of set families that have the consecutive-ones property, and a linear time algorithm to find the forbidden substructure if a set family does not have the property. The forbidden substructure has size O(n), where n is the size of the domain. The PQ tree is a well-known data structure for representing all consecutive-ones orderings. We show that it is given by a substitution decomposition of arbitrary set families that has not been described previously. This observation gives a generalization of the PQ tree to arbitrary set families, and we give a linear-time algorithm to compute it.