Bressan Marco
Dipartimento di Informatica, Università Statale di Milano, Milan, Italy.
Algorithmica. 2021;83(8):2578-2605. doi: 10.1007/s00453-021-00811-0. Epub 2021 Feb 22.
Given a -node pattern graph and an -node host graph , the subgraph counting problem asks to compute the number of copies of in . In this work we address the following question: can we count the copies of faster if is sparse? We answer in the affirmative by introducing a novel tree-like decomposition for directed acyclic graphs, inspired by the classic tree decomposition for undirected graphs. This decomposition gives a dynamic program for counting the homomorphisms of in by exploiting the degeneracy of , which allows us to beat the state-of-the-art subgraph counting algorithms when is sparse enough. For example, we can count the induced copies of any -node pattern in time if has bounded degeneracy, and in time if has bounded average degree. These bounds are instantiations of a more general result, parameterized by the degeneracy of and the structure of , which generalizes classic bounds on counting cliques and complete bipartite graphs. We also give lower bounds based on the Exponential Time Hypothesis, showing that our results are actually a characterization of the complexity of subgraph counting in bounded-degeneracy graphs.
给定一个(k)节点模式图(P)和一个(n)节点宿主图(G)，子图计数问题要求计算(G)中(P)的副本数量。在这项工作中，我们解决以下问题：如果(P)是稀疏的，我们能否更快地计数其副本？我们通过引入一种新颖的有向无环图的树状分解给出肯定答案，该分解受无向图的经典树分解启发。这种分解通过利用(P)的退化性给出了一个用于计算(G)中(P)同态的动态规划，当(P)足够稀疏时，这使我们能够超越当前最先进的子图计数算法。例如，如果(P)具有有界退化性，我们可以在(O(n^k))时间内计数任何(k)节点模式(P)的诱导副本；如果(P)具有有界平均度，则可以在(O(n^{\frac{k}{2}}))时间内计数。这些界限是一个更一般结果的实例化，该结果由(P)的退化性和结构参数化，它推广了关于计数团和完全二分图的经典界限。我们还基于指数时间假设给出了下界，表明我们的结果实际上是有界退化图中子图计数复杂性的一种刻画。
