Efficient detection and protection of information in cross tabulated tables II: Minimal linear invariants

To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells. A linear combination of the suppressed cells is called a linear invariant if it has a unique feasible value. Intuitively, the information contained in a linear invariant is not protected because its value can be uniquely determined. Using a decomposition approach, this paper establishes a fundamental correspondence between linear invariants of a table and edge cuts of a graph induced from the table. This correspondence is employed to give a linear-time algorithm for finding an important class of linear invariants called the row or column linear invariants. In subsequent papers, this correspondence is used to solve via graph theoretic techniques a wide variety of problems for protecting information in a table.