标题： 无交叉多流及其在不相交路径中的应用 显示英文标题

标题： Uncrossed Multiflows and Applications to Disjoint Paths

摘要： 在一个平面图中的多流是不交叉的，如果其支持路径所标识的曲线在平面上不交叉。 这样的流在以前的路由算法中发挥了作用，包括Schrijver的同伦方法和有向平面单源实例中的不可分割流。 最近，不交叉流在完全平面实例中最大不相交路径的近似算法中起到了关键作用，其中总供应量加需求图是平面的。 在完全平面的情况下，任何分数多流都可以转换为一个不交叉的多流，然后被用来找到分数解的良好舍入。 我们研究在一般平面实例（不一定完全平面）中寻找一个不交叉的多流作为一个独立的算法问题。 我们考虑了两种模型：一种是给定的需求必须全部被路由的拥挤模型，另一种是最大化模型，目标是在供应图中尽可能多地打包流（不一定公平）。 对于拥挤模型，我们证明确定一个实例是否存在不交叉（分数）多流是NP难的，但如果需求跨越有限数量的面，找到一个整数不交叉流的问题可以在多项式时间内解决。 对于最大化模型，我们提出了一个很强的（几乎多项式）近似无解结果。 关于整数性差距，对于最大化问题，我们证明在一个平面实例中的不交叉多流可以始终被舍入为一个整数多流，其值为原值的一个常数比例。 这在边容量和节点容量设置中都成立，并推广了对完全平面实例的先前界限。 在拥挤模型中，给定一个不交叉的分数多流，我们提供了一个舍入过程，该过程产生一个具有边拥挤度2的整数多流，可以通过额外的加法误差使它不可分割，该误差为最大需求。 显示英文摘要

摘要： 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.