首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:The Complexity of Average-Case Dynamic Subgraph Countin
  • 本地全文:下载
  • 作者:Monika Henzinger ; Andrea Lincoln ; Barna Saha
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2021
  • 卷号:21
  • 语种:English
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:Statistics of small subgraph counts such as triangles, four-cycles, and s-t paths 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 \ErdRen~graph: each update selects a pair of vertices (uv) uniformly at random and flips the existence of the edge (uv) . We develop new lower bounds and matching algorithms in this model for counting four-cycles, counting triangles through a specified point s, or a random queried point, and st paths of length 3, 4 and 5. Our results indicate while computing st paths of length 3, and 4 are easy in the average case with O(1) update time (note that they are hard in the worst case), it becomes hard when considering st paths 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.
  • 关键词:average-case lower bounds;dynamic;fine-grained complexity
国家哲学社会科学文献中心版权所有