2026-07-24T01:24:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14177 2024-03-06T10:53:40Z ddc:004 open_access

Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders Roth, Marc Schmitt, Johannes Wellnitz, Philip Counting complexity parameterized complexity Tutte polynomial Given a graph property Φ, we consider the problem 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 EdgeSub(Φ) and of its counting problem #EdgeSub(Φ) with respect to both approximate and exact counting. We obtain a complete picture for minor-closed properties Φ: the decision problem EdgeSub(Φ) always admits an FPT ("fixed-parameter tractable") algorithm and the counting problem #EdgeSub(Φ) always admits an FPTRAS ("fixed-parameter tractable randomized approximation scheme"). For exact counting, we present an exhaustive and explicit criterion on the property Φ which, if satisfied, yields fixed-parameter tractability and otherwise #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 #EdgeSub(Φ) 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 #EdgeSub(Φ). This allows us to establish hardness of exact counting using the Complexity Monotonicity framework due to Curticapean, Dell and Marx (STOC'17). This approach does not only apply to #EdgeSub(Φ) but also to the more general problem of computing weighted linear combinations of subgraph counts. As a special case of such a linear combination, we introduce 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 parameterized complexity of computing the evaluation of T^k_G at every pair of rational coordinates (x,y). In particular, our results give a new proof for the #W[1]-hardness of the problem of counting k-forests in a graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marc Roth and Johannes Schmitt and Philip Wellnitz 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.108 urn:nbn:de:0030-drops-141778 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.108 eng https://creativecommons.org/licenses/by/4.0/legalcode