有界退化度图中线性时间子图计数的二分层级结构

《Journal of the ACM》:A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs

【字体: 大 中 小 】 时间:2026年09月21日 来源:Journal of the ACM 3.0

编辑推荐:

   **摘要** 子图与同态计数是基本的算法问题。给定一个常数大小的模式图 *H* 和一个大规模输入图 *G*,我们希望统计 *G* 中 *H*-同态/*H*-子图的数量。鉴于现实世界图数据规模的庞大性以及计数问题的实际应用价值,我们着重研究在什么条件下可以实现(近)线性时间算

  **摘要**子图与同态计数是基本的算法问题。给定一个常数大小的模式图 *H* 和一个大规模输入图 *G*,我们希望统计 *G* 中 *H*-同态/*H*-子图的数量。鉴于现实世界图数据规模的庞大性以及计数问题的实际应用价值,我们着重研究在什么条件下可以实现(近)线性时间算法。Chiba-Nishizeki(SICOMP 1985)的开创性工作表明,对于有界退化度的输入类,团计数和4-圈计数可以在线性时间内完成。近期工作(Bera 等人,SODA 2021,JACM 2022)证明了二分性定理,刻画了在有界退化度输入上 *H*-同态计数可以在线性时间内完成的模式 *H*。在另一端,Ne?et?il 和 Ossona de Mendez 利用其关于"稀疏性"的深层理论定义了有界扩张度图类(该类包含所有非平凡的次闭族)。他们证明,对于**所有** *H*,*H*-同态计数在有界扩张度输入上均可在线性时间内完成。那么二者之间的情形如何?对于特定的 *H*,我们能否刻画使 *H*-同态计数可以在线性时间内完成的输入类?我们发现了一个二分性定理的层级结构来回答上述问题。我们证明存在一个无穷序列的图类族 $\mathcal{G}_0 \supseteq \mathcal{G}_1 \supseteq \cdots \supseteq \mathcal{G}_\infty$,其中 $\mathcal{G}_0$ 是有界退化度类的族,$\mathcal{G}_\infty$ 是有界扩张度类的族。固定任一常数大小的模式图 *H*。设 *LICL*(*H*) 表示 *H* 中最长导出圈的长度。我们证明如下结论。若 *LICL*(*H*) < 3(*r* + 2),则 *H*-同态可在 $\mathcal{G}_r$ 中的输入上线性时间内计数。若 *LICL*(*H*) ≥ 3(*r* + 2),则(在细粒度复杂性猜想下)来自 $\mathcal{G}_r$ 的输入上 *H*-同态计数需要 $\Omega(n^{1+\gamma})$ 时间。(其中 *n* 表示输入图的顶点数,*γ* 为某个显式常数。)子图计数同样满足类似的分二性定理。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号