Optimal Sequential Flows

8^th October 2026, 11:00 Ashton 208
Patrick Totzke
Liverpool

Abstract

We provide a new algebraic technique to solve the sequential flow problem in polynomial space. The task is to maximise 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 generalises to multiple in/output vertices, as well as regular constraints.

Joint work with Hugo Gimbert and Corto Mascle. Presented at ICALP 2026.
DOI: 10.4230/LIPIcs.ICALP.2026.98 (https://doi.org/10.4230/LIPIcs.ICALP.2026.98)