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

11/06/2020
โˆ™
by   Marc Roth, et al.
โˆ™
0
โˆ™

Given a graph property ฮฆ, we consider the problem ๐™ด๐š๐š๐šŽ๐š‚๐šž๐š‹(ฮฆ), 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 ๐™ด๐š๐š๐šŽ๐š‚๐šž๐š‹(ฮฆ) and of its counting problem #๐™ด๐š๐š๐šŽ๐š‚๐šž๐š‹(ฮฆ) with respect to both approximate and exact counting. We obtain a complete picture for minor-closed properties ฮฆ: the decision problem ๐™ด๐š๐š๐šŽ๐š‚๐šž๐š‹(ฮฆ) always admits an FPT algorithm and the counting problem #๐™ด๐š๐š๐šŽ๐š‚๐šž๐š‹(ฮฆ) 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 #๐–ถ[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 #๐™ด๐š๐š๐šŽ๐š‚๐šž๐š‹(ฮฆ) that run in time f(k)ยท|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 #๐™ด๐š๐š๐šŽ๐š‚๐šž๐š‹(ฮฆ). 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).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset