Computing the Number of Induced Copies of a Fixed Graph in a Bounded Degree Graph
Viresh S. Patel, Guus Regts · Algorithmica · 2018
In this paper we show that for any graph H of order m and any graph G of order n and maximum degree $$\Delta $$ one can compute the number of subsets S of V(G) that induces a graph isomorphic to H in time $$O(c^m \cdot n )$$ for some constant $$c = c(\Delta ) >0$$ . This is essentially best possible (in the sense that there is no $$c^{o(m)}poly(n)$$ -time algorithm under the exponential time hypothesis).