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}(\hat{I}¦)$ for fixed graph properties $\hat{I}¦$: Given an input graph $G$ and $k\in \mathbb{N}$, count the $k$…