cs.DS — Data Structures and Algorithms
Deterministic almost-linear time for general matching and network flow
We give deterministic almost-linear-time algorithms for maximum-cardinality matching in general graphs and integral minimum-cost flow. With , both run in time for polynomially bounded integer flow data. Their circulation oracle charges every traversal of a returned walk. A clipped logarithmic potential handles flow thresholds under improving updates and maintains strong components under arc insertions. For subgraphs with degree bounds, two matching computations encode a factor of every feasible size. The underlying exchange argument also gives integral cardinality slices for capacitated factors and is compatible with sharp local rounding.