2026/07/17 by Ronald Katende
#cs.DS #cs.CC #math.CO
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 ≤ \rm Sym(O) be its holonomy subgroup, let F = \rm Fix(H), and let p be an H-invariant root distribution. For the induced empirical model, \rm NCF(e)=p(F), \rm CF(e)=1-p(F). Consequently, compatibility, F, and \rm CF(e) are computable in O(|O|(|V|+|E|)) 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 (|O|-1)|E| 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(|O|) 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 \rm CF < 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.