Finding induced subgraphs in scale-free inhomogeneous random graphs

DOI10.1007/978-3-319-92871-5_1zbMATH Open1511.05207arXiv1801.08293MaRDI QIDQ6296901FDOQ6296901

Authors: Ellen Cardinaels, Johan S. H. van Leeuwaarden, Clara Stegehuis 

Publication date: 25 January 2018

Abstract: 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(nk)$ 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.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

This page was built for publication: Finding induced subgraphs in scale-free inhomogeneous random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6296901)