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, 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.