On exploiting degeneracy to count subgraphs
share
Motivated by practical applications, we study the complexity of counting the copies of a k-node pattern graph H in an n-node graph G, parameterized by the degeneracy d of G. We develop the source tree decomposition of H, a tree decomposition designed to exploit the degeneracy of G algorithmically to count homomorphisms, and an associated measure of source-treewidth s(H). Combining a simple dynamic programming with inclusion-exclusion arguments, for any given H we can count the homomorphisms from H to G in time f(d,k) ·Õ(n^s(H)). This allows us to obtain fast algorithms by bounding s(H) for interesting classes of patterns. For instance, we can count the induced or non-induced copies of any pattern faster than the decades-old state-of-the-art O(n^ω k/3+2) algorithm of [Nešetřil et al., 1985] as long as d < n^0.721 or m < n^1.442, where m is the number of edges of G. We complement our upper bounds with almost-matching lower bounds based on the Exponential Time Hypothesis [Impagliazzo et al., 1998].
READ FULL TEXT