Finding induced subgraphs in scale-free inhomogeneous random graphs

Ellen Cardinaels, Johan S. H. van Leeuwaarden, Clara Stegehuis*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

23 Downloads (Pure)


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 k)$ time for small values of $k$. We test our algorithm on several real-world data sets.
Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publication15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings
EditorsAnthony Bonato, Pawel Pralat, Andrei Raigorodskii
Number of pages14
ISBN (Electronic)978-3-319-92871-5
ISBN (Print)978-3-319-92870-8
Publication statusPublished - 30 May 2018
Externally publishedYes
EventInternational Workshop on Algorithms and Models for the Web-Graph 2018 - Moscow, Russian Federation
Duration: 17 May 201818 May 2018


WorkshopInternational Workshop on Algorithms and Models for the Web-Graph 2018
Abbreviated titleWAW 2018
Country/TerritoryRussian Federation


  • cs.DS
  • math.CO


Dive into the research topics of 'Finding induced subgraphs in scale-free inhomogeneous random graphs'. Together they form a unique fingerprint.

Cite this