@online{Roth_arXiv2011.03433,
TITLE = {Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders},
AUTHOR = {Roth, Marc and Schmitt, Johannes and Wellnitz, Philip},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2011.03433},
EPRINT = {2011.03433},
EPRINTTYPE = {arXiv},
YEAR = {2020},
ABSTRACT = {Given a graph property $\Phi$, we consider the problem<br>$\mathtt{EdgeSub}(\Phi)$, where the input is a pair of a graph $G$ and a<br>positive integer $k$, and the task is to decide whether $G$ contains a $k$-edge<br>subgraph that satisfies $\Phi$. Specifically, we study the parameterized<br>complexity of $\mathtt{EdgeSub}(\Phi)$ and of its counting problem<br>$\#\mathtt{EdgeSub}(\Phi)$ with respect to both approximate and exact counting.<br>We obtain a complete picture for minor-closed properties $\Phi$: the decision<br>problem $\mathtt{EdgeSub}(\Phi)$ always admits an FPT algorithm and the<br>counting problem $\#\mathtt{EdgeSub}(\Phi)$ always admits an FPTRAS. For exact<br>counting, we present an exhaustive and explicit criterion on the property<br>$\Phi$ which, if satisfied, yields fixed-parameter tractability and otherwise<br>$\#\mathsf{W[1]}$-hardness. Additionally, most of our hardness results come<br>with an almost tight conditional lower bound under the so-called Exponential<br>Time Hypothesis, ruling out algorithms for $\#\mathtt{EdgeSub}(\Phi)$ that run<br>in time $f(k)\cdot|G|^{o(k/\log k)}$ for any computable function $f$.<br> As a main technical result, we gain a complete understanding of the<br>coefficients of toroidal grids and selected Cayley graph expanders in the<br>homomorphism basis of $\#\mathtt{EdgeSub}(\Phi)$. This allows us to establish<br>hardness of exact counting using the Complexity Monotonicity framework due to<br>Curticapean, Dell and Marx (STOC'17). Our methods can also be applied to a<br>parameterized variant of the Tutte Polynomial $T^k_G$ of a graph $G$, to which<br>many known combinatorial interpretations of values of the (classical) Tutte<br>Polynomial can be extended. As an example, $T^k_G(2,1)$ corresponds to the<br>number of $k$-forests in the graph $G$. Our techniques allow us to completely<br>understand the parametrized complexity of computing the evaluation of $T^k_G$<br>at every pair of rational coordinates $(x,y)$.<br>},
}