有界退化度图中线性时间子图计数的二分层级结构
《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号