Finding induced subgraphs in scale-free inhomogeneous random graphs

01/25/2018

∙

by   Ellen Cardinaels, et al.

∙

0

∙

share

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.