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

@misc{lee2026exact,
  title = {{Exact volume computation for Boolean quadric polytopes of series-parallel graphs}},
  author = {Jon Lee},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.00734},
  eprint = {2610.00734},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.00734},
}

TY  - UNPB
TI  - Exact volume computation for Boolean quadric polytopes of series-parallel graphs
AU  - Jon Lee
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.00734
UR  - https://arxiv.org/abs/2610.00734
AB  - 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∈ 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 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 ℓ cut off at most a fraction 2^ℓ−1/ℓ! of Q(G). Hence vol(P(G))/vol(Q(G)) ≥ 1−∑_C 2^|C|−1/|C|! 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_ℓ it decays like ρ_ℓ^k for an explicit rational ρ_ℓ below the ratio of C_ℓ. 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.
ER  -