Abstract: 
Consider a convex relaxation f̂ of a pseudoBoolean function f. We say that the relaxation is totally halfintegral if f̂(x) is a polyhedral function with halfintegral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1x j, and x i=γ where γ∈{0,1,1/2} is a constant. A wellknown example is the roof duality relaxation for quadratic pseudoBoolean functions f. We argue that total halfintegrality is a natural requirement for generalizations of roof duality to arbitrary pseudoBoolean functions. Our contributions are as follows. First, we provide a complete characterization of totally halfintegral relaxations f̂ by establishing a onetoone correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally halfintegral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higherorder terms. This can be viewed as a nonsubmodular analogue of the fact that submodular functions generalize the st minimum cut problem with nonnegative weights to higherorder terms.
