Finding induced subgraphs in scale-free inhomogeneous random graphs

We study the induced subgraph isomorphism problem on inhomogeneous random graphs with infinite variance power-law degrees. We provide a fast algorithm that determines for any connected graph $H$ on $k$ vertices if it exists as induced subgraph in a random graph with $n$ vertices. By exploiting the scale-free graph structure, the algorithm runs in $O(n e^{k^4})$ time, and finds for constant $k$ an instance of $H$ in linear time with high probability.