Booth and Leuker [22] developed a data structure called the PQ tree, which they used to compute a column ordering that proves that that a binary matrix M has the COP. To define the PQ tree, it is convenient to reformulate the COP problem as follows: Let U be the set of columns of M. Let r be the number of rows in M. For each i, 1 ≤ i ≤ r, define the set Si to be the set of columns in U that have a one in row i. We seek a permutation of the elements of U that satisfies r restrictions, where restriction i, 1 ≤ i ≤ r requires that the elements of Si be consecutive in the permutation.