Counting Small Induced Subgraphs: Hardness of Symmetry-Based Properties

Radu Curticapean, Mingjun Liu

Jerrum and Meeks (TOCT, JCSS 2015) introduced the counting problems $\text{IndSub}(\Phi )$ for fixed graph properties $\Phi$: Given an input graph $G$ and $k\in \mathbb{N}$, count the $k$-v…