Parameterized Streaming: Maximal Matching and Vertex Cover
Parameterized Streaming: Maximal Matching and Vertex Cover
复制标题
参数化流：最大匹配和顶点覆盖
DOI：
10.1137/1.9781611973730.82
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Morteza Monemizadeh
中科院分区：
文献类型：
--
作者：
Rajesh Hemant Chitnis;Graham Cormode;Mohammad Taghi Hajiaghayi;Morteza Monemizadeh
随着图表规模的不断增长，我们寻求有效处理此类数据的方法。流图处理的模型，其中一个紧凑的摘要保持为每个边插入/删除观察，是一个有吸引力的。然而，很少有结果是已知的优化问题，这样的动态图streams.In本文中，我们引入了一种新的方法来处理图streams. By，而不是寻求解决方案的参数化版本的这些问题。在这里，我们给出一个参数k，目标是决定是否有一个解有界于k。通过将核化技术与随机草图结构相结合，我们获得了最大匹配和顶点覆盖的参数化版本的第一个流算法。我们考虑各种模型的图形流onnodes：只插入模型的边缘只能被添加，和动态模型的边缘可以被插入和删除。更正式地说，我们展示了以下结果：在只插入模型中，参数化顶点覆盖问题有一个一次通过的确定性算法，该算法使用k2空间1计算草图，使得在时间戳（2k）中的每个时间戳，它可以为当前实例提取最多k大小的解决方案，或者报告不存在这样的解决方案。在动态模型中，在每个时间戳上最多有一个最大匹配大小k的条件下，存在一个单通道（k2）空间（基于草图）动态算法，它在最坏情况下的更新时间戳（k2）上保持最大匹配。该算法部分解决了文献[1]中的公开问题64。这种动态匹配算法的应用是用于参数化顶点覆盖问题的单通道（k2）空间流算法，其在时间间隔（2k）中以概率1 - δ/no（1）提取最终实例的解，其中δ< 1。据我们所知，这是第一个图流算法，它将线性绘制与依赖于当前时刻图的顺序操作相结合，在没有任何承诺的动态模型中对于参数化的顶点覆盖问题，有一个一次通过的随机算法，该算法使用nk（nk）空间计算草图，使得在时间上（nk +2k）它可以为最终实例提取大小至多为k的解，或者报告不存在这样的解。
As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as each edge insertion/deletion is observed, is an attractive one. However, few results are known for optimization problems over such dynamic graph streams.In this paper, we introduce a new approach to handling graph streams, by instead seeking solutions for the parameterized versions of these problems. Here, we are given a parameterkand the objective is to decide whether there is a solution bounded byk. By combining kernelization techniques with randomized sketch structures, we obtain the first streaming algorithms for the parameterized versions of Maximal Matching and Vertex Cover. We consider various models for a graph stream onnnodes: the insertion-only model where the edges can only be added, and the dynamic model where edges can be both inserted and deleted. More formally, we show the following results:In the insertion only model, there is a one-pass deterministic algorithm for the parameterized Vertex Cover problem which computes a sketch usingÕ(k2) space1such that at each timestamp in timeÕ(2k) it can either extract a solution of size at mostkfor the current instance, or report that no such solution exists. We also show a tight lower bound of Ω(k2) for the space complexity of any (randomized) streaming algorithms for the parameterized Vertex Cover, even in the insertion-only model.In the dynamic model, and under thepromisethat at each timestamp there is a maximal matching of size at mostk, there is a one-passÕ(k2)-space (sketch-based) dynamic algorithm that maintains a maximal matching with worst-case update timeÕ(k2). This algorithm partially solves Open Problem 64 from [1]. An application of this dynamic matching algorithm is a one-passÕ(k2)-space streaming algorithm for the parameterized Vertex Cover problem that in timeÕ(2k) extracts a solution for the final instance with probability 1 – δ/no(1),whereδ< 1. To the best of our knowledge, this is the first graph streaming algorithm that combines linear sketching with sequential operations that depend on the graph at the current time.In the dynamic model without any promise, there is a one-pass randomized algorithm for the parameterized Vertex Cover problem which computes a sketch usingÕ(nk) space such that in timeÕ(nk +2k) it can either extract a solution of size at mostkfor the final instance, or report that no such solution exists.
登录
查看更多内容
DOI：
10.1145/1806689.1806753
发表时间：
2010
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
Krzysztof Onak;R. Rubinfeld
通讯作者：
R. Rubinfeld
用于完全动态最大匹配的简单确定性算法
影响因子：
4.4
作者：
Ofer Neiman;Shay Solomon
通讯作者：
Shay Solomon
O (log n) 更新时间内的完全动态最大匹配
DOI：
--
发表时间：
2011
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Surender Baswana;Manoj Gupta;Sandeep Sen
通讯作者：
Sandeep Sen
流上的图挖掘
DOI：
10.1007/978-0-387-39940-9_184
发表时间：
2009
期刊：
Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
A. Mcgregor
通讯作者：
A. Mcgregor
用于近似最小顶点覆盖尺寸的近最优次线性时间算法
影响因子：
1.1
作者：
Krzysztof Onak;D. Ron;M. Rosen;R. Rubinfeld
通讯作者：
R. Rubinfeld