The Complexity of Average-Case Dynamic Subgraph Counting
The Complexity of Average-Case Dynamic Subgraph Counting
复制标题
平均情况动态子图计数的复杂性
DOI：
10.1137/1.9781611977073.23
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
and Saha, Barna
中科院分区：
文献类型：
--
作者：
Henzinger, Monika;Lincoln, Andrea;and Saha, Barna
小的子图计数，如三角形，四圈，和短长度的s-tpath的统计揭示了重要的结构特性的基础图。这些问题在社会网络分析中得到了广泛的研究。在大多数相关应用中，图形不仅庞大，而且会随着时间的推移而动态变化。当考虑最坏情况时，这些问题中的大多数在动态设置中变得困难。在本文中，我们提出了一个问题，即在平均情况下，动态图上的小子图计数问题是否也是困难的，我们考虑了一个最简单的可能的平均情况模型，其中更新遵循Erdens-Rényi图：每个更新随机均匀地选择一对顶点（u，v），并翻转边（u，v）的存在性。在这个模型中，我们开发了新的下界和匹配算法，用于计算四个循环，计算通过指定点或随机查询点的三角形，以及长度为3，4和5的stpath。我们的结果表明，当计算长度为3和4的路径时，在平均情况下是容易的，更新时间为O（1）（注意，在最坏情况下它们是困难的），当计算长度为5的路径时，它就变得困难了。我们引入了新的技术，使我们能够从在线矩阵向量问题（OMv）的最坏情况硬度得到这些图问题的平均情况硬度。我们的技术依赖于细粒度平均情况复杂性的最新进展。我们的技术推进了这一文献，给出了证明平均情况下的动态算法的新下界的能力。
Statistics of small subgraph counts such as triangles, four-cycles, ands-tpaths of short lengths reveal important structural properties of the underlying graph. These problems have been widely studied in social network analysis. In most relevant applications, the graphs are not only massive but also change dynamically over time. Most of these problems become hard in the dynamic setting when considering the worst case. In this paper, we ask whether the question of small subgraph counting over dynamic graphs is hard also in the average case.We consider the simplest possible average case model where the updates follow an Erdős-Rényi graph: each update selects a pair of vertices (u, v) uniformly at random and flips the existence of the edge (u, v). We develop new lower bounds and matching algorithms in this model for counting four-cycles, counting triangles through a specified points, or a random queried point, andstpaths of length 3, 4 and 5. Our results indicate while computingstpaths of length 3, and 4 are easy in the average case withO(1) update time (note that they are hard in the worst case), it becomes hard when consideringstpaths of length 5.We introduce new techniques which allow us to get average-case hardness for these graph problems from the worst-case hardness of the Online Matrix vector problem (OMv). Our techniques rely on recent advances in fine-grained average-case complexity. Our techniques advance this literature, giving the ability to prove new lower bounds on average-case dynamic algorithms.
登录
查看更多内容
维护更新下的三角查询
DOI：
10.1145/3396375
发表时间：
2020
期刊：
ACM Transactions on Database Systems (TODS)
影响因子：
--
作者：
A. Kara;Milos Nikolic;H. Ngo;Dan Olteanu;Haozhe Zhang
通讯作者：
Haozhe Zhang
动态图算法的平均情况分析
影响因子：
1.1
作者：
David Alberts;Monika Henzinger
通讯作者：
Monika Henzinger
证明细粒度平均表面硬度的新技术
DOI：
10.1109/focs46700.2020.00077
发表时间：
2020
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Dalirrooyfard, Mina;Lincoln, Andrea;Williams, Virginia Vassilevska
通讯作者：
Williams, Virginia Vassilevska
全动态四顶点子图计数
DOI：
--
发表时间：
2021
期刊：
Symposium on Algorithmic Foundations of Dynamic Networks
影响因子：
--
作者：
Kathrin Hanauer;Monika Henzinger;Q. Hua
通讯作者：
Q. Hua
数据流模型中的三角和四周期计数
DOI：
10.1145/3375395.3387652
发表时间：
2020
期刊：
PODS 2020
影响因子：
--
作者：
McGregor, Andrew;Vorotnikova, Sofya
通讯作者：
Vorotnikova, Sofya