论文标题
平面和有界形状图中的包装周期
Packing cycles in planar and bounded-genus graphs
论文作者
论文摘要
我们设计了恒定的因子近似算法，以在给定平面或有界形式图中找到与某个循环家族的尽可能多的分离周期。在这里，脱节可能意味着顶点 - 界限或边缘 - 界定，并且图形可能是无方向性的或指向的。所考虑的周期家族必须满足两种特性：必须是不可折磨的，并允许在给定的非负边缘重量或（在平面图中）在删除给定的子集后，该家族中所有剩余周期的联合。 我们的设置概括了过去分别研究的许多问题。例如，满足上述特性的三个家族是（i）在有向或无向图中的所有循环，（ii）所有奇数循环中的所有奇数循环中的所有奇数循环，（iii）在无向图中的所有循环完全包含一个需求边缘，其中需求边缘构成边缘集的子集。后一个家族（III）对应于完全平面和有界的类型实例中的经典脱节路径问题。尽管在这种情况下，对于边缘 - 偶会路径的恒定因子近似算法是已知的，但我们在平面情况下改善了常数，并获得了首先的顶点 - 分散路径的算法。我们还获得了ERDőS-Pósa类型的大约最小值定理。例如，平面挖掘物中设置的最小反馈顶点最多是顶点 - 偶数周期数的最大数量。
We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here disjoint can mean vertex-disjoint or edge-disjoint, and the graph can be undirected or directed. The family of cycles under consideration must satisfy two properties: it must be uncrossable and allow for an oracle access that finds a weight-minimal cycle in that family for given nonnegative edge weights or (in planar graphs) the union of all remaining cycles in that family after deleting a given subset of edges. Our setting generalizes many problems that were studied separately in the past. For example, three families that satisfy the above properties are (i) all cycles in a directed or undirected graph, (ii) all odd cycles in an undirected graph, and (iii) all cycles in an undirected graph that contain precisely one demand edge, where the demand edges form a subset of the edge set. The latter family (iii) corresponds to the classical disjoint paths problem in fully planar and bounded-genus instances. While constant-factor approximation algorithms were known for edge-disjoint paths in such instances, we improve the constant in the planar case and obtain the first such algorithms for vertex-disjoint paths. We also obtain approximate min-max theorems of the Erdős--Pósa type. For example, the minimum feedback vertex set in a planar digraph is at most 12 times the maximum number of vertex-disjoint cycles.
