Felix Reidl

A color-avoiding approach to subgraph counting in bounded expansion classes

2020 · arXiv (Cornell University)

We present an algorithm to count the number of occurrences of a pattern graph $H$ as an induced subgraph in a host graph $G$. If $G$ belongs to a bounded expansion class, the algorithm runs …