Roth, Marc ;
Schmitt, Johannes ;
Wellnitz, Philip
Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders
Abstract
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 kedge 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 minorclosed properties Φ: the decision problem EdgeSub(Φ) always admits an FPT ("fixedparameter tractable") algorithm and the counting problem #EdgeSub(Φ) always admits an FPTRAS ("fixedparameter tractable randomized approximation scheme"). For exact counting, we present an exhaustive and explicit criterion on the property Φ which, if satisfied, yields fixedparameter tractability and otherwise #W[1]hardness. Additionally, most of our hardness results come with an almost tight conditional lower bound under the socalled 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 kforests 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 kforests in a graph.
BibTeX  Entry
@InProceedings{roth_et_al:LIPIcs.ICALP.2021.108,
author = {Roth, Marc and Schmitt, Johannes and Wellnitz, Philip},
title = {{Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {108:1108:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14177},
URN = {urn:nbn:de:0030drops141778},
doi = {10.4230/LIPIcs.ICALP.2021.108},
annote = {Keywords: Counting complexity, parameterized complexity, Tutte polynomial}
}
02.07.2021
Keywords: 

Counting complexity, parameterized complexity, Tutte polynomial 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 