Finding induced subgraphs in scale-free inhomogeneous random graphs

We study the problem of finding a copy of a specific induced subgraph on inhomogeneous random graphs with infinite variance power-law degrees. We provide a fast algorithm that finds a copy of any connected graph \(H\) on a fixed number of \(k\) vertices as an induced subgraph in a random graph with \(n\) vertices. By exploiting the scale-free graph structure, the algorithm runs in \(O(n k)\) time for small values of \(k\). As a corollary, this shows that the induced subgraph isomorphism problem can be solved in time \(O(nk)\) for the inhomogeneous random graph. We test our algorithm on several real-world data sets.