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.