{"id":"arxiv/2611.12330","url":"https://arxiv.org/abs/2611.12330","tags":["math.CO","cs.DM"],"score":0,"title":"Cut Conditions, Integrality, and Obstructions for Directed Multiflows","domain":"math.CO","source":"arxiv","authors":["Srinwanti Debgupta","Martin Skutella","Philipp Warode"],"reviews":0,"subject":"math.CO","summary":"In contrast to the max-flow/min-cut theorem for single-commodity flows, the cut condition is necessary but not sufficient for the existence of directed multiflows, even with only two commodities. Poremba and Shepherd (IPCO 2023) conjecture that the cut condition is sufficient for all capacities and demands on a directed two-commodity topology if and only if it contains neither of two specific topologies as a relevant minor. We prove this conjecture. As a consequence, the fractional and integral flow-cut gaps of every directed two-commodity topology coincide and are either 1 or 2. We then…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-09","reactions":{}}