Minimum Support Augmentation in Chordal Graphical Models

Given an observed support in a finite Cartesian table, we minimize the number of distinct new cells needed to make every maximal-clique projection of a chordal graphical model surjective. For a clique path, the missing clique configurations form a partially ordered set, and the minimum augmentation equals its width. This gives an exact algorithm by bipartite matching, as well as an equivalent lower-bound circulation formulation. In contrast, the decision problem is NP-complete on the fixed six-variable chordal graph with maximal cliques ABC, ABX, ACY, and BCZ, even when X, Y, Z are binary; the alphabets of A, B, C are allowed to grow. A partial Latin square supplies the reduction and a concrete support for which the three individual root-leaf optima are five but the global optimum is six. Integer separator multiplicities also give an exact dynamic program on any clique tree. The statistical interpretation uses the classical positive-MLE criterion for decomposable models. The explicitly stated augmentation results are complete; the general AIM marginal-cone facet question is not resolved. This AI-assisted, self-audited preprint is unrefereed and makes no claim of absolute priority.