{"id":"arxiv/2610.00734","url":"https://arxiv.org/abs/2610.00734","tags":["math.OC","math.CO"],"score":0,"title":"Exact volume computation for Boolean quadric polytopes of series-parallel graphs","domain":"math.OC","source":"arxiv","authors":["Jon Lee"],"reviews":0,"subject":"math.OC","summary":"For a graph G, the Boolean quadric polytope P(G) is the convex hull of the binary solutions of $y_{ij}=x_ix_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=|V(G)|+|E(G)|$, we compute it with $O(d^7)$ arithmetic operations, and $O(d^5)$ if…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}