Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders

Marc Roth, Johannes Schmitt, Philip Wellnitz

Given a graph property $\Phi$, we consider the problem $\mathtt{EdgeSub}(\Phi )$, where the input is a pair of a graph $G$ and a positive integer $k$, and the task is to decide whether $G…