Can You Link Up With Treewidth?
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908366080573440 |
|---|---|
| author | Curticapean, Radu Döring, Simon Neuen, Daniel Wang, Jiaheng |
| author_facet | Curticapean, Radu Döring, Simon Neuen, Daniel Wang, Jiaheng |
| contents | In a fundamental paper in parameterized complexity theory, Marx [ToC '10] constructed $k$-vertex graphs $H$ of maximum degree $3$ such that $n^{o(k /\log k)}$ time algorithms for detecting colorful $H$-subgraphs would refute the Exponential-Time Hypothesis (ETH). This result is widely used to obtain almost-tight conditional lower bounds for parameterized problems under ETH.
We give a new and fully self-contained proof of this result that further simplifies a recent work by Karthik et al. [SOSA 2024]. In our proof, we introduce a novel graph parameter of independent interest, the linkage capacity $γ(H)$, and show that detecting colorful $H$-subgraphs in time $n^{o(γ(H))}$ refutes ETH. Then, we use a simple construction of communication networks credited to Beneš to obtain $k$-vertex graphs of maximum degree $3$ and linkage capacity $Ω(k / \log k)$, avoiding arguments involving expander graphs, which were required in previous papers. We also show that every graph $H$ of treewidth $t$ has linkage capacity $Ω(t / \log t)$, thus recovering a stronger result shown by Marx [ToC '10] with a simplified proof.
Additionally, we obtain new tight lower bounds on the complexity of colorful subgraph detection for certain types of patterns by analyzing their linkage capacity: We prove that almost all $k$-vertex graphs of polynomial average degree $Ω(k^β)$ for $β> 0$ have linkage capacity $Θ(k)$, which implies tight lower bounds for finding such patterns $H$. As an application of these results, we also obtain tight lower bounds for counting small induced subgraphs having a fixed property $Φ$, improving bounds from, e.g., [Roth et al., FOCS 2020]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02606 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Can You Link Up With Treewidth? Curticapean, Radu Döring, Simon Neuen, Daniel Wang, Jiaheng Data Structures and Algorithms Computational Complexity In a fundamental paper in parameterized complexity theory, Marx [ToC '10] constructed $k$-vertex graphs $H$ of maximum degree $3$ such that $n^{o(k /\log k)}$ time algorithms for detecting colorful $H$-subgraphs would refute the Exponential-Time Hypothesis (ETH). This result is widely used to obtain almost-tight conditional lower bounds for parameterized problems under ETH. We give a new and fully self-contained proof of this result that further simplifies a recent work by Karthik et al. [SOSA 2024]. In our proof, we introduce a novel graph parameter of independent interest, the linkage capacity $γ(H)$, and show that detecting colorful $H$-subgraphs in time $n^{o(γ(H))}$ refutes ETH. Then, we use a simple construction of communication networks credited to Beneš to obtain $k$-vertex graphs of maximum degree $3$ and linkage capacity $Ω(k / \log k)$, avoiding arguments involving expander graphs, which were required in previous papers. We also show that every graph $H$ of treewidth $t$ has linkage capacity $Ω(t / \log t)$, thus recovering a stronger result shown by Marx [ToC '10] with a simplified proof. Additionally, we obtain new tight lower bounds on the complexity of colorful subgraph detection for certain types of patterns by analyzing their linkage capacity: We prove that almost all $k$-vertex graphs of polynomial average degree $Ω(k^β)$ for $β> 0$ have linkage capacity $Θ(k)$, which implies tight lower bounds for finding such patterns $H$. As an application of these results, we also obtain tight lower bounds for counting small induced subgraphs having a fixed property $Φ$, improving bounds from, e.g., [Roth et al., FOCS 2020]. |
| title | Can You Link Up With Treewidth? |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2410.02606 |