Background: In machine learning, we often work with graphical models to represent high dimensional probability density functions. If we discard the constraint that a density integrates (sums) to 1, we get an unnormalized graph-structured energy function.

Suppose we have such an energy function, $E$, defined on a graph $G = (\mathcal{V}, \mathcal{E})$. There is one variable $x$ for each vertex of the graph, and there are real-valued unary and pairwise functions, $\theta_i(x_i) : i \in \mathcal{V}$ and $\theta_{ij}(x_i, x_j) : ij \in \mathcal{E}$, respectively. The full energy is then

$$E(\mathbf{x}) = \sum_{i \in \mathcal{V}} \theta_i(x_i) + \sum_{ij \in \mathcal{E}} \theta_{ij}(x_i, x_j)$$

If all $x \in \mathbf{x}$ are binary, we can think of an $x$ as indicating set membership and with just a small abuse of terminology talk about submodularity. In this case, an energy function is submodular iff $\theta_{ij}(0, 0) + \theta_{ij}(1, 1) \le \theta_{ij}(0, 1) + \theta_{ij}(1, 0)$. We are typically interested in finding the configuration that minimizes the energy, $\mathbf{x}^* = \arg \min_{\mathbf{x}} E(\mathbf{x})$.

There seems to be a connection between minimizing a submodular energy function and monotone boolean functions: if we lower the energy of some $\theta_i(x_i=1)$ for any $x_i$ (i.e., increase its preference to be "true"), then the optimal assignment of any variable $x_i^* \in \mathbf{x}^*$ can only change from 0 to 1 ("false" to "true"). If all $\theta_i$ are restricted to be either 0 or 1, then we have $|\mathcal{V}|$ monotone boolean functions:

$$f_i(\mathbf{\theta}) = x_i^*$$

where as above, $\mathbf{x^*} = \arg \min_{\mathbf{x}} E(\mathbf{x})$.

Question: Can we represent all monotone boolean functions using this setup by varying the pairwise terms, $\theta_{ij}$? What if we allow $E$ to be an arbitrary submodular energy function? Conversely, can we represent all submodular minimization problems as a set of $|\mathcal{V}|$ monotone boolean functions?

Can you suggest references that will help me towards better understanding these connections? I'm not a theoretical computer scientist, but I'm trying to understand if there are insights about monotone boolean functions that are not captured by thinking in the submodular minimization terms.


1 Answer 1


As far as I understand, the submodular minimization case captures all there is to be said about the monotone Boolean case, and binary submodular Boolean functions can express all submodular Boolean functions. However, if the domain is non-Boolean, then binary submodular functions are not enough to express all submodular functions, even if hidden variables may be introduced. (Apologies if I have missed a subtlety in your precise problem phrasing.)

The state of the art is discussed in this nice paper which has lots of links to related work, and that also makes the links to computer vision quite explicit:

  • Stanislav Živný, David A. Cohen, Peter G. Jeavons, The expressive power of binary submodular functions, DAM 157 3347–3358, 2009. doi: 10.1016/j.dam.2009.07.001 (preprint)

In case your next question is about approximation, this recent paper looks at the approximation version:

  • Dorit S. Hochbaum, Submodular problems - approximations and algorithms, arXiv: 1010.1945

Edit: fixed link.

  • $\begingroup$ Although the (preprint) link takes me to a different paper than the doi: link does. $\endgroup$
    – dan_x
    Commented Oct 19, 2010 at 15:28
  • $\begingroup$ @dan x: fixed the link, thanks for the heads-up. $\endgroup$ Commented Oct 19, 2010 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.