Abstract
We study the problems of counting copies and induced copies of a small pattern graph H in a large host graph G. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns H. In this work, we address the more challenging task of analysing the complexity for restricted patterns and restricted hosts. Specifically we ask which families of allowed patterns and hosts imply fixedparameter tractability, i.e., the existence of an algorithm running in time f(H)⋅G^O(1) for some computable function f. Our main results present exhaustive and explicit complexity classifications for families that satisfy natural closure properties. Among others, we identify the problems of counting small matchings and independent sets in subgraphclosed graph classes ? as our central objects of study and establish the following crisp dichotomies as consequences of the Exponential Time Hypothesis:
 Counting kmatchings in a graph G ∈ ? is fixedparameter tractable if and only if ? is nowhere dense.
 Counting kindependent sets in a graph G ∈ ? is fixedparameter tractable if and only if ? is nowhere dense. Moreover, we obtain almost tight conditional lower bounds if ? is somewhere dense, i.e., not nowhere dense. These base cases of our classifications subsume a wide variety of previous results on the matching and independent set problem, such as counting kmatchings in bipartite graphs (Curticapean, Marx; FOCS 14), in Fcolourable graphs (Roth, Wellnitz; SODA 20), and in degenerate graphs (Bressan, Roth; FOCS 21), as well as counting kindependent sets in bipartite graphs (Curticapean et al.; Algorithmica 19).
At the same time our proofs are much simpler: using structural characterisations of somewhere dense graphs, we show that a colourful version of a recent breakthrough technique for analysing pattern counting problems (Curticapean, Dell, Marx; STOC 17) applies to any subgraphclosed somewhere dense class of graphs, yielding a unified view of our current understanding of the complexity of subgraph counting.
BibTeX  Entry
@InProceedings{bressan_et_al:LIPIcs.ITCS.2023.27,
author = {Bressan, Marco and Goldberg, Leslie Ann and Meeks, Kitty and Roth, Marc},
title = {{Counting Subgraphs in Somewhere Dense Graphs}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {27:127:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17530},
URN = {urn:nbn:de:0030drops175304},
doi = {10.4230/LIPIcs.ITCS.2023.27},
annote = {Keywords: counting problems, somewhere dense graphs, parameterised complexity theory}
}
Keywords: 

counting problems, somewhere dense graphs, parameterised complexity theory 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 