Lemma 8 ([Quantitative feasibility and bounded output denominators]). Every continuation step can be computed in polynomial binary time. Its returned variables may be taken on a fixed rational grid whose encoding length depends only on n+m …

We give deliberately loose uniform bounds. Put P=n+m+2≥5 and use the upper-triangular entries of the upper-left (n-1)×(n-1) block as free coordinates of a centered symmetric matrix. If that block is A , its full completion is CAC^T , where C=[e_1-e_n ⋯e_ n-1 -e_n] . Thus a free-coordinate perturbation of Euclidean norm η changes the full matrix in operator norm by at most 2Pη . Include λ,y,z as ordinary scalar coordinates. Their total number D is at most P^3 . A connected unweighted multigraph has λ_ (L_H|_ ^⊥ )≥P^ -3 =:μ, \|L_H\|_ ≤2m. For the first bound, for a centered unit vector choose its largest and smallest coordinates and a path between them of length at most n-1 . The coordinate range is at least n^ -1/2 , so Cauchy--Schwarz along that path already gives energy at least 1/(n(n-1))≥P^ -3 . Consider an auxiliary point, without requiring its partition constraints: Y_0=2L_H, λ_ ijk,0 =P^ -8 , y_ e,0 =P^ -8 , z_ e,0 =κ/2. There are at most P^3 generators, each of norm at most 6 , so their weighted sum has norm at most 6P^ -5 <μ/2 . Since s≤r^ 1/4 ≤m+1<P and \|b_eb_e^T\|=2 , the response LMI at this point has margin at least 2μ-12P^ -7 >μ . The other two LMIs have margins at least μ/2 . The λ and lower y faces have margin P^ -8 , the upper y face has margin at least 1/2 , and the z lower and upper faces have margins at least κ/2 and 1 , respectively. Finally κ+u_e+t(5y_ e,0 -4)-z_ e,0 ≥κ/2-4t=3κ/8. All scalar normal norms and affine matrix Lipschitz constants are at most 20P^3 in these coordinates. It follows that the entire ball of radius ρ_0=P^ -20 about this auxiliary point satisfies all non-packing constraints. In particular these estimates are uniform even when an active u_e is extremely small. By Lemma 6 ([A feasible continuation response]), choose a stronger feasible point x_* , using z_e=a_e(y) and any representation . Let β=grt . Every nontrivial partition has slack at least β(| P|-1)≥β at x_* relative to. Moreover, β≥1 32(m+1) ≥1 32P . At the auxiliary point every such slack is at least -P^2 , because all capacities are nonnegative and Q^+≤r≤m . Mix a fraction θ=P^ -8 of the auxiliary point into x_* . Since P≥5 , the new partition slacks are at least (1-θ)β-θP^2≥β/2 . Convexity gives a ball of radius θρ_0=P^ -28 satisfying the non-packing constraints about the mixture. A partition normal has at most m unit coefficients in the z coordinates, so its norm is at most √m . Thus the smaller ball of radius ρ=P^ -30 satisfies every partition constraint as well. Their exponential number does not change this uniform estimate. There is also a uniform outer ball. Testing against the centered identity gives Y≤6m . Taking traces in the second LMI of gives ∑λ_ ijk ≤3m . Together with 0≤y_e≤1 and 0≤z_e≤κ+1≤2 , these bounds place all free coordinates in the ball of radius P^3 . We may impose the larger radius 2P^3 with slack. This ball also has an exact rational separator: for a rational query a with \|a\|>R , the inequality a·x≤(R^2+\|a\|^2)/2 contains the radius- R ball and strictly excludes a , by Cauchy--Schwarz and the arithmetic--geometric mean inequality. All ball constants have logarithmic encoding length in P . The rational central-cut ellipsoid procedure, using Lemma 7 ([Partition separation by minimum spanning trees]), now finds an exactly feasible point in polynomial work . Indeed, use our exact membership test at every oracle query and choose the enclosing-volume cutoff below (2ρ/D)^D , the volume of a coordinate cube contained in the proved radius- ρ inner ball. The small-volume outcome is impossible, so the algorithm must terminate at an exactly accepted rational point. This argument uses the displayed positive inradius; it does not assume exact solvability of an arbitrary semidefinite feasibility problem. To bound the returned denominators independently of those in u , put L=_2P , η=2^ -32L and γ=2^ -36L , and instead find x such that x±ηe_j∈ F (1≤j≤D), where F is the full step feasible set, including the outer bound. The intersection of these 2D translates still contains a ball of radius at least ρ-η≥3ρ/4 , and has a separation oracle by translating the queries. Use the corresponding volume cutoff with 3ρ/4 in place of ρ . Convexity implies that the cross-polytope x+v:\|v\|_1≤η lies in F . Round each coordinate of x to the fixed dyadic mesh γ . Its total rounding error is at most Dγ/2≤η/(2P)<η , so the rounded point remains feasible. The outer bound gives at most 39L+O(1) bits per coordinate. This argument does not round a boundary solution without a margin. Finally s and Q have polynomial encoding length throughout the prescribed schedule. At a rational X L_H , its centered inverse and all old u_e are computed exactly with polynomial bit operations. Every new Y lies on the fixed grid just described. Forming X^+=(1-t)X+tY increases encoding length by only a polynomial additive amount per step. Over the polynomial number of steps neither denominators nor oracle work can cascade beyond polynomial size.