Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles
Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles
复制标题
有界简并图中的近线性时间同态计数：长诱导循环的障碍
DOI：
10.1137/1.9781611976465.138
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Seshadhri, C.
中科院分区：
文献类型：
--
作者：
Bera, Suman K.;Pashanasangi, Noujan;Seshadhri, C.
计算定长模式图的同态在输入图G中是一个基本的计算问题。在输入G和模式H的各种约束下，研究这个问题的复杂性已经有了很长的历史。考虑到这个问题的重要性和现代输入的巨大规模，我们研究了何时可能实现近线性时间算法。我们主要讨论当输入图具有有界退化时的情况，这是同态计数中一类通常研究和实际相关的问题。从前人的工作可知，对于某些h类，H-同态在有界退化图中可以在近线性时间内精确计数。我们能精确地刻画出模式H的近线性时间算法吗？我们完全解决了这个问题，使用细粒度的复杂性发现了一个干净的二分法。让我们表示边数。证明了：如果H中的最大诱导圈的长度不超过5，则有界退化图中存在计数H-同态的ANO(Mlogm)算法。如果H中的最大诱导圈的长度至少为6，则(假设标准细粒度复杂性猜想)存在一个常数γ>；0，使得不存在计数H-同态的(M1+γ)时间算法。
Counting homomorphisms of a constant sized pattern graphHin an input graphGis a fundamental computational problem. There is a rich history of studying the complexity of this problem, under various constraints on the inputGand the patternH. Given the significance of this problem and the large sizes of modern inputs, we investigate when near-linear time algorithms are possible. We focus on the case when the input graph has bounded degeneracy, a commonly studied and practically relevant class for homomorphism counting. It is known from previous work that for certain classes ofH, H-homomorphisms can be counted exactly in near-linear time in bounded degeneracy graphs. Can we precisely characterize the patternsHfor which near-linear time algorithms are possible?We completely resolve this problem, discovering a clean dichotomy using fine-grained complexity. Letmdenote the number of edges inG. We prove the following: if the largest induced cycle inHhas length at most 5, then there is anO(mlogm) algorithm for countingH-homomorphisms in bounded degeneracy graphs. If the largest induced cycle inHhas length at least 6, then (assuming standard fine-grained complexity conjectures) there is a constantγ> 0, such that there is noo(m1+γ) time algorithm for countingH-homomorphisms.
登录
查看更多内容
DOI：
10.4230/lipics.icalp.2020.11
发表时间：
2019-05
期刊：
ArXiv
影响因子：
--
作者：
Suman Kalyan Bera;Amit Chakrabarti;Prantar Ghosh
通讯作者：
Suman Kalyan Bera;Amit Chakrabarti;Prantar Ghosh
DOI：
--
发表时间：
2006
期刊：
International Workshop on Graph-Theoretic Concepts in Computer Science
影响因子：
--
作者：
Gaurav Goel;J. Gustedt
通讯作者：
J. Gustedt
DOI：
10.1109/focs.2015.44
发表时间：
2015-04
期刊：
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
T. Eden;Amit Levi;D. Ron;C. Seshadhri
通讯作者：
T. Eden;Amit Levi;D. Ron;C. Seshadhri
计算数据流中的任意子图
DOI：
--
发表时间：
2012
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
D. Kane;K. Mehlhorn;Thomas Sauerwald;He Sun
通讯作者：
He Sun
DOI：
10.1016/j.tcs.2004.08.008
发表时间：
2004
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
V. Dalmau;P. Jonsson
通讯作者：
P. Jonsson