Contextual Fraction on Permutation Gain Graphs: Exact Algorithms, Query Lower Bounds, and Dynamic Maintenance

For an explicitly represented finite empirical model, deciding whether the contextual fraction is strictly below one is NP-complete, while the standard exact linear program has one column for every global assignment. We identify a permutation-transport class in which this global problem collapses to a fixed-point calculation. Let a connected permutation gain graph act on a finite state set $O$, let $H\le \mathrm{S}\mathrm{y}\mathrm{m}(O)$ be its holonomy subgroup, let $F=\mathrm{F}\mathrm{i}\mathrm{x}(H)$, and let $p$ be an $H$-invariant root distribution. For the induced empirical model, $$\mathrm{N}\mathrm{C}\mathrm{F}(e)=p(F),\mathrm{C}\mathrm{F}(e)=1-p(F)\mathrm{.}$$ Consequently, compatibility, $F$, and $\mathrm{C}\mathrm{F}(e)$ are computable in $O(\mathrm{\mid }O\mathrm{\mid }(\mathrm{\mid }V\mathrm{\mid }+\mathrm{\mid }E\mathrm{\mid }))$ arithmetic and table operations. For every finite simple $2$-edge-connected graph, any deterministic exact algorithm in the explicit permutation-table query model requires at least $(\mathrm{\mid }O\mathrm{\mid }-1)\mathrm{\mid }E\mathrm{\mid }$ probes in the worst case, making the dependence on the input tables optimal up to constant factors. With a fixed spanning tree, chord insertions and deletions require $O(\mathrm{\mid }O\mathrm{\mid })$ worst-case time, or time proportional to the moved-set representation, while compatibility and contextual-fraction queries take $O(1)$ time. Finally, for common-marginal realizable binary constraint languages, the support threshold $\mathrm{C}\mathrm{F}<1$ is polynomial-time equivalent to the associated finite-domain constraint-satisfaction problem and therefore inherits the Bulatov–Zhuk dichotomy. The results identify a query-optimal and dynamically maintainable tractability island inside the general contextual-fraction problem.