Low-Step Multi-commodity Flow Emulators

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.

Authors

• Bernhard Haeupler
• D. Ellis Hershkowitz
• Jason Li 0006
• Antti Roeyskoe
• Thatchaphol Saranurak

Keywords

• flow emulators
• hopsets
• multi-commodity flows