论文标题
检测和计数小的子图，并评估参数化的Tutte多项式：通过环形网格和Cayley Graph Expanders的下限
Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders
论文作者
论文摘要
给定图形属性$φ$，我们考虑了问题$ \ mathtt {edgesub}（φ）$，其中输入是一对graph $ g $和一个正整数$ k $，而任务是确定$ g $是否包含满足$φ$的$ k $ - edge-gended子Graph。具体而言，我们研究了$ \ mathtt {edgeSub}（φ）$的参数化复杂性及其计数问题$ \＃\ mathtt {edgeSub}（φ）$相对于近似计数和精确计数。我们获得了次要属性$φ$的完整图片：决策问题$ \ mathtt {edgesub}（φ）$始终允许fpt算法和计数问题$ \＃\＃\ mathtt {edgesub}（φ）$始终接纳fptras。对于确切的计数，我们在属性$φ$上提出了一个详尽而明确的标准，如果满足，该标准会产生固定参数的拖延性，否则$ \＃\ \＃\ Mathsf {w [1]} $ - 硬度。此外，我们的大多数硬度结果都带有所谓的指数时间假设下的几乎有条件的下限，排除了$ \ \＃\＃\ mathtt {edgesub}（φ）$的算法，该算法在时间$ f（k）\ cdot | g | g |^{k/\ log k）$ for任何计算功能$ f $ f $ f（k）\ cdot | g | g | 作为主要技术结果，我们以$ \＃\＃\ mathtt {edgeSub}（φ）$的同构基础的基础上的同构基础上的同构基础上有完整的了解环形网格的系数和选定的Cayley图扩展器。这使我们能够使用Curticapean，Dell和Marx（Stoc'17）引起的复杂性单调性框架建立精确计数的硬度。我们的方法也可以应用于图$ g $的Tutte多项式$ t^k_g $的参数化变体，许多已知的组合解释可以扩展（经典）Tutte多项式的值。例如，$ t^k_g（2,1）$对应于图$ g $中的$ k $ forest的数量。我们的技术使我们能够完全理解每对有理坐标$（x，y）$在计算$ t^k_g $评估的参数化复杂性。
Given a graph property $Φ$, we consider the problem $\mathtt{EdgeSub}(Φ)$, where the input is a pair of a graph $G$ and a positive integer $k$, and the task is to decide whether $G$ contains a $k$-edge subgraph that satisfies $Φ$. Specifically, we study the parameterized complexity of $\mathtt{EdgeSub}(Φ)$ and of its counting problem $\#\mathtt{EdgeSub}(Φ)$ with respect to both approximate and exact counting. We obtain a complete picture for minor-closed properties $Φ$: the decision problem $\mathtt{EdgeSub}(Φ)$ always admits an FPT algorithm and the counting problem $\#\mathtt{EdgeSub}(Φ)$ always admits an FPTRAS. For exact counting, we present an exhaustive and explicit criterion on the property $Φ$ which, if satisfied, yields fixed-parameter tractability and otherwise $\#\mathsf{W[1]}$-hardness. Additionally, most of our hardness results come with an almost tight conditional lower bound under the so-called Exponential Time Hypothesis, ruling out algorithms for $\#\mathtt{EdgeSub}(Φ)$ that run in time $f(k)\cdot|G|^{o(k/\log k)}$ for any computable function $f$. As a main technical result, we gain a complete understanding of the coefficients of toroidal grids and selected Cayley graph expanders in the homomorphism basis of $\#\mathtt{EdgeSub}(Φ)$. This allows us to establish hardness of exact counting using the Complexity Monotonicity framework due to Curticapean, Dell and Marx (STOC'17). Our methods can also be applied to a parameterized variant of the Tutte Polynomial $T^k_G$ of a graph $G$, to which many known combinatorial interpretations of values of the (classical) Tutte Polynomial can be extended. As an example, $T^k_G(2,1)$ corresponds to the number of $k$-forests in the graph $G$. Our techniques allow us to completely understand the parametrized complexity of computing the evaluation of $T^k_G$ at every pair of rational coordinates $(x,y)$.
