Listing 6-Cycles in Sparse Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913610571186176 |
|---|---|
| author | Williams, Virginia Vassilevska Westover, Alek |
| author_facet | Williams, Virginia Vassilevska Westover, Alek |
| contents | This work considers the problem of output-sensitive listing of occurrences of $2k$-cycles for fixed constant $k\geq 2$ in an undirected host graph with $m$ edges and $t$ $2k$-cycles. Recent work of Jin and Xu (and independently Abboud, Khoury, Leibowitz, and Safier) [STOC 2023] gives an $O(m^{4/3}+t)$ time algorithm for listing $4$-cycles, and recent work by Jin, Vassilevska Williams and Zhou [SOSA 2024] gives an $\widetilde{O}(n^2+t)$ time algorithm for listing $6$-cycles in $n$ node graphs. We focus on resolving the next natural question: obtaining listing algorithms for $6$-cycles in the sparse setting, i.e., in terms of $m$ rather than $n$. Previously, the best known result here is the better of Jin, Vassilevska Williams and Zhou's $\widetilde{O}(n^2+t)$ algorithm and Alon, Yuster and Zwick's $O(m^{5/3}+t)$ algorithm.
We give an algorithm for listing $6$-cycles with running time $\widetilde{O}(m^{1.6}+t)$. Our algorithm is a natural extension of Dahlgaard, Knudsen and Stöckel's [STOC 2017] algorithm for detecting a $2k$-cycle. Our main technical contribution is the analysis of the algorithm which involves a type of ``supersaturation'' lemma relating the number of $2k$-cycles in a bipartite graph to the sizes of the parts in the bipartition and the number of edges. We also give a simplified analysis of Dahlgaard, Knudsen and Stöckel's $2k$-cycle detection algorithm (with a small polylogarithmic increase in the running time), which is helpful in analyzing our listing algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07499 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Listing 6-Cycles in Sparse Graphs Williams, Virginia Vassilevska Westover, Alek Data Structures and Algorithms This work considers the problem of output-sensitive listing of occurrences of $2k$-cycles for fixed constant $k\geq 2$ in an undirected host graph with $m$ edges and $t$ $2k$-cycles. Recent work of Jin and Xu (and independently Abboud, Khoury, Leibowitz, and Safier) [STOC 2023] gives an $O(m^{4/3}+t)$ time algorithm for listing $4$-cycles, and recent work by Jin, Vassilevska Williams and Zhou [SOSA 2024] gives an $\widetilde{O}(n^2+t)$ time algorithm for listing $6$-cycles in $n$ node graphs. We focus on resolving the next natural question: obtaining listing algorithms for $6$-cycles in the sparse setting, i.e., in terms of $m$ rather than $n$. Previously, the best known result here is the better of Jin, Vassilevska Williams and Zhou's $\widetilde{O}(n^2+t)$ algorithm and Alon, Yuster and Zwick's $O(m^{5/3}+t)$ algorithm. We give an algorithm for listing $6$-cycles with running time $\widetilde{O}(m^{1.6}+t)$. Our algorithm is a natural extension of Dahlgaard, Knudsen and Stöckel's [STOC 2017] algorithm for detecting a $2k$-cycle. Our main technical contribution is the analysis of the algorithm which involves a type of ``supersaturation'' lemma relating the number of $2k$-cycles in a bipartite graph to the sizes of the parts in the bipartition and the number of edges. We also give a simplified analysis of Dahlgaard, Knudsen and Stöckel's $2k$-cycle detection algorithm (with a small polylogarithmic increase in the running time), which is helpful in analyzing our listing algorithm. |
| title | Listing 6-Cycles in Sparse Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.07499 |