Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial

Radu Curticapean, Simon Döring, Daniel Neuen

We consider the parameterized problem $\#$IndSub$(\Phi )$ for fixed graph properties $\Phi$: Given a graph $G$ and an integer $k$, this problem asks to count the number of induced $k$-ver…