Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155717 |
| _version_ | 1824458041248972800 |
|---|---|
| author | Dalirrooyfard, Mina Mathialagan, Surya Williams, Virginia Vassilevska Xu, Yinzhan |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Dalirrooyfard, Mina Mathialagan, Surya Williams, Virginia Vassilevska Xu, Yinzhan |
| author_sort | Dalirrooyfard, Mina |
| collection | MIT |
| description | STOC ’24, June 24–28, 2024, Vancouver, BC, Canada |
| first_indexed | 2024-09-23T10:52:46Z |
| format | Article |
| id | mit-1721.1/155717 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:19:35Z |
| publishDate | 2024 |
| publisher | ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing |
| record_format | dspace |
| spelling | mit-1721.1/1557172024-12-21T05:58:44Z Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques Dalirrooyfard, Mina Mathialagan, Surya Williams, Virginia Vassilevska Xu, Yinzhan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory STOC ’24, June 24–28, 2024, Vancouver, BC, Canada We study the problem of nding and listing -cliques in an -edge, -vertex graph, for constant ≥ 3. This is a fundamental problem of both theoretical and practical importance. Our rst contribution is an algorithmic framework for nding -cliques that gives the rst improvement in 19 years over the old runtimes for 4 and 5-clique nding, as a function of [Eisenbrand and Grandoni, TCS’04]. With the current bounds on matrix multiplication, our algorithms run in (1.66) and (2.06) time, respectively, for 4-clique and 5-clique nding. Our main contribution is an output-sensitive algorithm for listing -cliques, for any constant ≥ 3. We complement the algorithm with tight lower bounds based on standard ne-grained assumptions. Previously, the only known conditionally optimal outputsensitive algorithms were for the case of 3-cliques given by Björklund, Pagh, Vassilevska W. and Zwick [ICALP’14]. If the matrix multiplication exponent is 2, and if the number of -cliques is large enough, the running time of our algorithms is ˜ min{ 1 −2 1− 2 (−2) , 2 −1 1− 2 (−1) } , and this is tight under the Exact--Clique Hypothesis. This running time naturally extends the running time obtained by Björklund, Pagh, Vassilevska W. and Zwick for = 3. Our framework is very general in that it gives -clique listing algorithms whose running times can be measured in terms of the number of ℓ-cliques Δℓ in the graph for any 1 ≤ ℓ < . This generalizes the typical parameterization in terms of (the number of 1-cliques) and (the number of 2-cliques). If is 2, and if the size of the output, Δ , is su ciently large, then for every ℓ < , the running time of our algorithm for listing -cliques is ˜ Δ 2 ℓ(−ℓ) ℓ Δ 1− 2 (−ℓ) 2024-07-19T14:30:19Z 2024-07-19T14:30:19Z 2024-06-10 2024-07-01T07:48:19Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155717 Dalirrooyfard, Mina, Mathialagan, Surya, Williams, Virginia Vassilevska and Xu, Yinzhan. 2024. "Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques." PUBLISHER_CC en 10.1145/3618260.3649663 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing Association for Computing Machinery |
| spellingShingle | Dalirrooyfard, Mina Mathialagan, Surya Williams, Virginia Vassilevska Xu, Yinzhan Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques |
| title | Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques |
| title_full | Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques |
| title_fullStr | Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques |
| title_full_unstemmed | Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques |
| title_short | Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques |
| title_sort | towards optimal output sensitive clique listing or listing cliques from smaller cliques |
| url | https://hdl.handle.net/1721.1/155717 |
| work_keys_str_mv | AT dalirrooyfardmina towardsoptimaloutputsensitivecliquelistingorlistingcliquesfromsmallercliques AT mathialagansurya towardsoptimaloutputsensitivecliquelistingorlistingcliquesfromsmallercliques AT williamsvirginiavassilevska towardsoptimaloutputsensitivecliquelistingorlistingcliquesfromsmallercliques AT xuyinzhan towardsoptimaloutputsensitivecliquelistingorlistingcliquesfromsmallercliques |