论文标题
围绕桥梁：网络设计中的统一概念
Bridge Girth: A Unifying Notion in Network Design
论文作者
论文摘要
Althőfer等人的1993年经典论文。事实证明，跨度，仿真器和距离甲骨文降低了高圆形图的极端功能$γ$。本文启动了网络设计中的大量作品，其中问题会减少到$γ$或其他周长概念的类似极端功能来攻击问题。在本文中，我们介绍并研究了一个新的周长概念，该概念称为路径系统的桥梁围栏，我们表明它可以用来显着扩展和改善围栏问题和网络设计之间的连接网络。我们证明了两种结果： 1）我们编写了$ n $ node的最大可能大小，$ p $ - Paths系统，带有桥梁的周长$> k $为$β（n，p，k）$，我们为$β^*（n，p，k）$编写了某种变体。我们在文献中确定了一些参数，这些论点暗示了$β，β^*$上的上限或下限，并且我们为这些界限提供了一些多项式改进。特别是，我们以$β（n，p，2）$构建一个紧密的下限，并且我们以$β（n，p，4）$和$β^*（n，p，\ f，\ infty）$的多项式改善上限。 2）我们表明，通过将黑盒减少到$β$或$β^*$，可以恢复或改进网络设计中的许多最新结果。示例包括距离/可及性保存器的边界，精确的跳动组，快捷套装，定向多刺和最稀疏的切口的流缝间隙，定向Steiner Forest的完整性差距。 我们认为，围墙的概念可以导致研究领域的更强大，更有条理的地图。在此方面，我们留下了许多开放问题，这与围绕高架围墙的路径系统大小相关的桥梁围绕围墙的缩小和极端界限有关。
A classic 1993 paper by Althőfer et al. proved a tight reduction from spanners, emulators, and distance oracles to the extremal function $γ$ of high-girth graphs. This paper initiated a large body of work in network design, in which problems are attacked by reduction to $γ$ or the analogous extremal function for other girth concepts. In this paper, we introduce and study a new girth concept that we call the bridge girth of path systems, and we show that it can be used to significantly expand and improve this web of connections between girth problems and network design. We prove two kinds of results: 1) We write the maximum possible size of an $n$-node, $p$-path system with bridge girth $>k$ as $β(n, p, k)$, and we write a certain variant for "ordered" path systems as $β^*(n, p, k)$. We identify several arguments in the literature that implicitly show upper or lower bounds on $β, β^*$, and we provide some polynomially improvements to these bounds. In particular, we construct a tight lower bound for $β(n, p, 2)$, and we polynomially improve the upper bounds for $β(n, p, 4)$ and $β^*(n, p, \infty)$. 2) We show that many state-of-the-art results in network design can be recovered or improved via black-box reductions to $β$ or $β^*$. Examples include bounds for distance/reachability preservers, exact hopsets, shortcut sets, the flow-cut gaps for directed multicut and sparsest cut, an integrality gap for directed Steiner forest. We believe that the concept of bridge girth can lead to a stronger and more organized map of the research area. Towards this, we leave many open problems, related to both bridge girth reductions and extremal bounds on the size of path systems with high bridge girth.
