Skip to content

Minimizing Hidden Binary Submodular Energy Preserves Submodularity

Claim/Theorem

Let V and H be finite sets, and let

\[ E:\{0,1\}^{V\sqcup H}\to \mathbb R \]

be a submodular function on all visible and hidden coordinates. Define

\[ f(x):=\min_{y\in\{0,1\}^{H}} E(x,y) \qquad (x\in\{0,1\}^{V}). \]

Then f is submodular on the visible coordinates. In particular, every Boolean function representable by binary submodular functions with auxiliary variables is itself submodular on its visible variables.

This is a derived closure statement.

For arbitrary visible assignments x,x', choose hidden minimizers y,y' such that

\[ f(x)=E(x,y), \qquad f(x')=E(x',y'). \]

Since E is submodular on V\sqcup H,

\[ E(x,y)+E(x',y') \ge E(x\wedge x',\,y\wedge y') + E(x\vee x',\,y\vee y'). \]

By definition of f,

\[ E(x\wedge x',\,y\wedge y')\ge f(x\wedge x'), \qquad E(x\vee x',\,y\vee y')\ge f(x\vee x'). \]

Combining the two displays gives

\[ f(x)+f(x') \ge f(x\wedge x')+f(x\vee x'), \]

which is exactly visible submodularity of f.

Finally, any hidden-vertex binary-submodular representation is a finite sum of binary submodular terms followed by minimization over the auxiliary variables. Sums of submodular functions are submodular, so the closure statement applies.

Dependencies

  • [[boolean-network-generalization-adds-no-nonmonotone-power-for-stabilizer-cut-rank.md]]

Conflicts/Gaps

  • This gives only a necessary condition for hidden-vertex graph-cut expressibility, not a sufficient one.
  • It does not classify which visible submodular functions admit realizations with bounded auxiliary budget.
  • The node is used here as a generic obstruction tool: any visibly non-submodular candidate function is automatically excluded from binary submodular hidden-vertex expressibility.

Sources

  • 10.1016/j.dam.2009.07.001
  • 10.1007/s10878-017-0136-y