Generalized roof duality and bisubmodular functions

Consider a convex relaxation $\hat f$ of a pseudo-boolean function $f$. We say that the relaxation is {\em totally half-integral} if $\hat f(\bx)$ is a polyhedral function with half-integral extreme points $\bx$, 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 \gamma$ where $\gamma\in\{0,1,\frac{1}{2}\}$ is a constant. A well-known example is the {\em 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.