Low-Step Multi-commodity Flow Emulators
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Roeyskoe, Thatchaphol Saranurak · 2024
We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous flow decomposition barrier for multi-commodity flow.