Vertex Sparsification for Edge Connectivity
Vertex Sparsification for Edge Connectivity
复制标题
DOI：
10.1137/1.9781611976465.74
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Parinya Chalermsook;Syamantak Das;Bundit Laekhanukit;Yunbum Kook;Yang P. Liu;Richard Peng;Mark Sellke-Mark-Sell
中科院分区：
文献类型：
--
作者：
Parinya Chalermsook;Syamantak Das;Bundit Laekhanukit;Yunbum Kook;Yang P. Liu;Richard Peng;Mark Sellke-Mark-Sell
图的压缩或稀疏化是一个基本的信息论和计算问题。在这个研究领域的一个主要的开放问题是是否存在$（1+\n）$-近似割保持顶点稀疏的大小接近终端的数量。作为实现这一目标的一步，我们研究了一个阈值版本的问题：对于一个给定的参数$c$，找到一个更小的图，我们称之为连通性-$c$模仿网络，它保留了$k$终端之间的连通性，直到$c$的值。我们证明了具有$O（kc^4）$边的连通性-$c$模仿网络存在，并且可以在时间$m（c\log n）^{O（c）}$中找到。我们还给出了一个单独的算法，构造这样的图与$k \cdot O（c）^{2c}$边在时间$mc^{O（c）}\log^{O（1）}n$。这些结果导致的第一个数据结构回答完全动态离线$c$-边连接查询为$c \ge 4$在多对数时间每个查询，以及更有效的算法生存网络设计有界树宽图。
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter $c$, find a smaller graph, which we call connectivity-$c$ mimicking network, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist and can be found in time $m(c\log n)^{O(c)}$. We also give a separate algorithm that constructs such graphs with $k \cdot O(c)^{2c}$ edges in time $mc^{O(c)}\log^{O(1)}n$. These results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c \ge 4$ in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.