arXiv:2611.03858 · v1

A Family of Well-Behaved Multiflow Instances

首次提交 2026-11-03 03:31

版本更新 2026-11-03 03:31

雷达观测 2026-11-04 23:40

摘要

We introduce a family of cut-sufficient instances for undirected multiflow that generalizes single-source planar and fully-planar instances. We also show the family has an additive $6 d_{\max}$ error for converting a fractional flow into an unsplittable one.

作者备注：To appear in SOSA 2027. 10 pages, 2 figures