Contextual Fraction on Permutation Gain Graphs: Exact Algorithms, Query Lower Bounds, and Dynamic Maintenance
Data Structures and AlgorithmsComputational Complexity
Summary
The authors study a problem about deciding how "contextual" a certain mathematical model is, which is generally very hard (NP-complete). They identify a special case, called the permutation-transport class, where this complicated problem can be simplified into a fixed-point calculation that is much faster. This allows them to compute important values efficiently and maintain those computations quickly even as the model changes. They also show some lower bounds on the number of queries needed to solve the problem exactly, and link the problem to known classifications in constraint satisfaction problems. Overall, the authors find a specific setting where a normally difficult problem becomes tractable and manageable.
Authors
Ronald Katende
Abstract
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 \leq{ \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),\qquad {\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.