2024/07/09 by Radu Curticapean, Curticapean, Radu, Daniel Neuen +1 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Machine Learning and Data Classification
paper · pdf · doi:10.48550/arxiv.2407.07051
openalex publication_date 2024/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a fixed graph property Φ and integer k ≥ 1, consider the problem of counting the induced k-vertex subgraphs satisfying Φ in an input graph G. This problem can be solved by brute-force in time O(nk). Under ETH, we prove several lower bounds on the optimal exponent in this running time: If Φ is edge-monotone (i.e., closed under deleting edges), then ETH rules out no(k) time algorithms for this problem. This strengthens a recent lower bound by Döring, Marx and Wellnitz [STOC 2024]. Our result also holds for counting modulo fixed primes. If at most (2-ε)^\binomk2 graphs on k vertices satisfy Φ, for some ε > 0, then ETH also rules out an exponent of o(k). This holds even when the graphs in Φ have arbitrary individual weights, generalizing previous results for hereditary properties by Focke and Roth [SIAM J. Comput. 2024]. If Φ is non-trivial and excludes βΦ edge-densities, then the optimal exponent under ETH is Ω(βΦ). This holds even when the graphs in Φ have arbitrary individual weights, generalizing previous results by Roth, Schmitt and Wellnitz [SIAM J. Comput. 2024]. In all cases, we also obtain #W[1]-hardness if k is part of the input and considered as the parameter. We also obtain lower bounds on the Weisfeiler-Leman dimension. As opposed to the nontrivial techniques from combinatorics, group theory, and simplicial topology used before, our results follow from a relatively straightforward ``algebraization'' of the problem in terms of polynomials, combined with applications of simple algebraic facts, which can also be interpreted in terms of Fourier analysis.