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

Abstract

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 x_{i}=x_{j}, x_{i}=1-x_{j}, and x_{i}=γ 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.