Uncrossed Multiflows and Applications to Disjoint Paths

A multiflow in a planar graph is uncrossed if the curves identified by its support paths do not cross in the plane. Such flows have played a role in previous routing algorithms, including Schrijver's Homotopy Method and unsplittable flows in directed planar single-source instances. Recently uncrossed flows have played a key role in approximation algorithms for maximum disjoint paths in fully-planar instances, where the combined supply plus demand graph is planar. In the fully-planar case, any fractional multiflow can be converted into one that is uncrossed, which is then exploited to find a good rounding of the fractional solution. We investigate finding an uncrossed multiflow as a standalone algorithmic problem in general planar instances (not necessarily fully-planar). We consider both a congestion model where the given demands must all be routed, and a maximization model where the goal is to pack as much flow in the supply graph as possible (not necessarily equitably). For the congestion model, we show that determining if an instance has an uncrossed (fractional) multiflow is NP-hard, but the problem of finding an integral uncrossed flow is polytime solvable if the demands span a bounded number of faces. For the maximization model, we present a strong (almost polynomial) inapproximability result. Regarding integrality gaps, for maximization we show that an uncrossed multiflow in a planar instance can always be rounded to an integral multiflow with a constant fraction of the original value. This holds in both the edge-capacitated and node-capacitated settings, and generalizes earlier bounds for fully-planar instances. In the congestion model, given an uncrossed fractional multiflow, we give a rounding procedure that produces an integral multiflow with edge congestion 2, which can be made unsplittable with an additional additive error of the maximum demand.