Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
复制标题
DOI：
10.1137/1.9781611974331.ch92
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova
中科院分区：
文献类型：
--
作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova
在本文中，我们提出了一个简单但功能强大的子图采样原始词，适用于各种计算模型，包括动态图流（其中输入图由边缘/超越插入和删除的序列定义）以及MapReduce等分布式系统。在动态图流的情况下，我们使用此原始性来证明以下结果：•匹配：我们的匹配项的主要结果是存在O（k2）空间算法，该算法返回在基础上返回最大匹配的边缘最多是k存在一个O（N2/α3）空间算法，该算法在独立工作中返回α-approximation我们的精确和近似算法与平面图这样的均匀匹配，可以进一步降低恒定近似所需的空间。 •顶点盖和击打集：存在O（KD）空间算法，该算法解决了最小击球设置问题，其中D是输入集的基数，K是最小击球集的上限是对数因素的最佳选择。其他）为此，我们的子绘制原始样品会产生快速的小空间动态图流算法。
In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input graph is defined by a sequence of edge/hyperedge insertions and deletions) and distributed systems such as MapReduce. In the case of dynamic graph streams, we use this primitive to prove the following results: • Matching: Our main result for matchings is that there exists an O(k2) space algorithm that returns the edges of a maximum matching on the assumption the cardinality is at most k. The best previous algorithm used O(kn) space where n is the number of vertices in the graph and we prove our result is optimal up to logarithmic factors. Our algorithm has O(1) update time. We also show that there exists an O(n2/α3) space algorithm that returns an α-approximation for matchings of arbitrary size. In independent work, Assadi et al. (SODA 2016) proved this approximation algorithm is optimal and provided an alternative algorithm. We generalize our exact and approximate algorithms to weighted matching. For graphs with low arboricity such as planar graphs, the space required for constant approximation can be further reduced. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first non-trivial results in the dynamic setting. • Vertex Cover and Hitting Set: There exists an O(kd) space algorithm that solves the minimum hitting set problem where d is the cardinality of the input sets and k is an upper bound on the size of the minimum hitting set. We prove this is optimal up to logarithmic factors. Our algorithm has O(1) update time. The case d = 2 corresponds to minimum vertex cover. Finally, we consider a larger family of parameterized problems (including b-matching, disjoint paths, vertex coloring among others) for which our subgraph sampling primitive yields fast, small-space dynamic graph stream algorithms. We then show lower bounds for natural problems outside this family.