Generalized roof duality and bisubmodular functions

Vladimir Kolmogorov.

In Discrete Applied Mathematics, March 2012, 160(4-5):416-426.
Preliminary version appeared in Neural Information Processing Systems Conference (NIPS), December 2010.


Consider a convex relaxation F of a pseudo-boolean function f. We say that the relaxation is totally half-integral if F(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form xi=xj, xi=1-xj, and xi where γ ∈ {0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-boolean functions.

Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations F by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality.


doi link
arXiv version