Exact volume computation for Boolean quadric polytopes of series-parallel graphs

For a graph G, the Boolean quadric polytope P(G) is the convex hull of the binary solutions of $y_{ij}=x_i{x}_j$ for $ij\in E(G)$, and Q(G) is its standard linear relaxation. For series-parallel graphs, Q(G) together with the odd-cycle inequalities describes P(G). Lee and Skipper showed vol(Q(G)) is polynomial-time computable for bounded treewidth and gave a closed formula for vol(P(G)) when G is a cycle. We resolve their question of giving an efficient algorithm for vol(P(G)) on series-parallel graphs. With $d=\mathrm{\mid }V(G)\mathrm{\mid }+\mathrm{\mid }E(G)\mathrm{\mid }$, we compute it with $O(d^7)$ arithmetic operations, and $O(d^5)$ if G is a cactus. The algorithm is a dynamic program over the series-parallel decomposition. The same framework computes vol(Q(G)) (hence the number of linear extensions of the incidence poset of G) with $O(d^4)$ operations, and $O(d^3)$ for cacti. With every $x_v$ fixed at 1/2, the recursion reduces to convolutions of univariate polynomials and computes the cut polytope volume of every series-parallel graph with m edges in $O(m^3)$ operations. We also study how much of Q(G) the polytope P(G) occupies. Short odd cycles matter more than long ones: in every graph, the odd-cycle inequalities of a cycle of length $\mathrm{\ell }$ cut off at most a fraction $2^{\mathrm{\ell }-1}\mathrm{/}\mathrm{\ell }!$ of Q(G). Hence vol(P(G))/vol(Q(G)) $\ge 1-{\sum }_C{2}^{\mathrm{\mid }C\mathrm{\mid }-1}\mathrm{/}\mathrm{\mid }C\mathrm{\mid }!$ for series-parallel G, with C ranging over its cycles. The ratio does not factor over cycles sharing a vertex: in a flower of $k$ copies of $C_{\mathrm{\ell }}$ it decays like ${\rho }_{\mathrm{\ell }}^k$ for an explicit rational ${\rho }_{\mathrm{\ell }}$ below the ratio of $C_{\mathrm{\ell }}$. Nevertheless, the small fractions cut off by many long cycles compound: in the worst case, triangle inequalities, or odd-cycle inequalities up to any fixed length, close no fixed fraction of the gap between Q(G) and P(G), and the volume ratio can be exponentially small in d.