2025/11/17 by Gimbert, Hugo, Mascle, Corto, Totzke, Patrick
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2511.13806
We provide a new algebraic technique to solve the sequential flow problem in polynomial space. The task is to maximize the flow through a graph where edge capacities can be changed over time by choosing a sequence of capacity labelings from a given finite set. Our method is based on a novel factorization theorem for finite semigroups that, applied to a suitable flow semigroup, allows to derive small witnesses. This generalizes to multiple in/output vertices, as well as regular constraints.