On degeneracy and the parameterized complexity of subgraph counting
share
We study the complexity of counting the (induced) occurrences of a k-node pattern graph in an n-node graph, parameterized by the degeneracy d of the latter. We introduce the piece decomposition of a pattern graph H together with its piecewidth p(H). These two notions capture the parameterized complexity of counting H: we give a dynamic programming algorithm based on the piece decomposition that counts the occurrences of H in time f(d,k) ·Õ(n^ p(H)), and prove that unless the Exponential Time Hypothesis fails, no algorithm exists with running time f(d,k) · n^o(p(H)/p(H)). By bounding p(H) we obtain novel complexity bounds. On the one hand we prove that cliques minus c edges can be counted in time f(d,k) ·Õ(n^ 1/2 + √(c/2)), which generalizes the well-known O(nd^k-1) upper bound for counting cliques, and shows that a lower degeneracy makes it easier to find and count dense patterns. Then we prove that any pattern on k nodes can be counted in time f(k) ·Õ(n^ k/4 +2 d^k- k/4 -2), beating the classic O(n^(ω k / 3)+2) bound for d < n^0.721 using the current matrix multiplication exponent ω≈ 2.37. On the other hand we show that algorithms with running time f(d,k) · n^o(k/k) are unlikely to exist, even for d=2.
READ FULL TEXT