Counting Small Induced Subgraphs: Hardness via Fourier Analysis
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911310992637952 |
|---|---|
| author | Curticapean, Radu Neuen, Daniel |
| author_facet | Curticapean, Radu Neuen, Daniel |
| contents | For a fixed graph property $Φ$ and integer $k \geq 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(n^{k})$. 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 $n^{o(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-\varepsilon)^{\binom{k}{2}}$ graphs on $k$ vertices satisfy $Φ$, for some $\varepsilon > 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 $\mathsf{\#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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_07051 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Counting Small Induced Subgraphs: Hardness via Fourier Analysis Curticapean, Radu Neuen, Daniel Computational Complexity Data Structures and Algorithms For a fixed graph property $Φ$ and integer $k \geq 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(n^{k})$. 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 $n^{o(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-\varepsilon)^{\binom{k}{2}}$ graphs on $k$ vertices satisfy $Φ$, for some $\varepsilon > 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 $\mathsf{\#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. |
| title | Counting Small Induced Subgraphs: Hardness via Fourier Analysis |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.07051 |