2023/11/15 by Döring, Simon, Marx, Dániel, Wellnitz, Philip · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.08988
We study the parameterized complexity of #IndSub(Φ), where given a graph G and an integer k, the task is to count the number of induced subgraphs on k vertices that satisfy the graph property Φ. Focke and Roth [STOC 2022] completely characterized the complexity for each Φ that is a hereditary property (that is, closed under vertex deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate cases when every graph satisfies Φ or only finitely many graphs satisfy Φ. We complement this result with a classification for each Φ that is edge monotone (that is, closed under edge deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate case when there are only finitely many integers k such that Φ is nontrivial on k-vertex graphs. Our result generalizes earlier results for specific properties Φ that are related to the connectivity or density of the graph. Further, we extend the #W[1]-hardness result by a lower bound which shows that #IndSub(Φ) cannot be solved in time f(k) ⋅ |V(G)|o(√(log k/loglog k)) for any function f, unless the Exponential-Time Hypothesis (ETH) fails. For many natural properties, we obtain even a tight bound f(k) ⋅ |V(G)|o(k); for example, this is the case for every property Φ that is nontrivial on k-vertex graphs for each k greater than some k0.