Volume computation for sparse Boolean quadric relaxations

Abstract Motivated by understanding the quality of tractable convex relaxations of intractable polytopes, Ko et al. gave a closed-form expression for the volume of a standard relaxation Q ( G ) of the Boolean quadric polytope (also known as the (full) correlation polytope) P ( G ) of the complete graph G = K n . We extend this work to structured sparse graphs. In particular, we (i) demonstrate the existence of an efficient algorithm for vol ( Q ( G ) ) when G has bounded treewidth, (ii) give closed-form expressions (and asymptotic behaviors) for vol ( Q ( G ) ) for all stars, paths, and cycles, and (iii) give a closed-form expression for vol ( P ( G ) ) for all cycles. Further, we demonstrate that when G is a cycle, the simple relaxation Q ( G ) is a very close model for the much more complicated P ( G ) . Additionally, we give some computational results demonstrating that this behavior of the cycle seems to extend to more complicated graphs. Finally, we speculate on the possibility of extending some of our results to cactii or even series–parallel graphs.