| 講演名 | 2021-03-08 [Invited Talk] Tight Distributed Listing of Cliques Keren Censor-Hillel(Technion), Yi-Jun Chang(ETH), Fran?ois Le Gall(名大), Dean Leitersdorf(Technion), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | Much progress has recently been made in understanding the complexity landscape of subgraph finding problems in the CONGEST model of distributed computing. However, so far, very few tight bounds are known in this area. For triangle (i.e., 3-clique) listing, an optimal $tilde{O}(n^{1/3})$-round distributed algorithm has been constructed by Chang et al. [SODA 2019, PODC 2019]. Recent works have shown sublinear algorithms for $K_p$-listing, for each $p geq 4$, but still leaving a significant gap between the upper bounds and the known lower bounds of the problem. In this work, we completely close this gap. We show that for each $p geq 4$, there is an $tilde{O}(n^{1 - 2/p})$-round distributed algorithm that lists all $p$-cliques $K_p$ in the communication network. Our algorithm is optimal up to a polylogarithmic factor, due to the $tilde{Omega}(n^{1 - 2/p})$-round lower bound of Fischer et al. [SPAA 2018], which holds even in the CONGESTED CLIQUE model. Together with the triangle-listing algorithm by Chang et al. [SODA 2019, PODC 2019], our result thus shows that the round complexity of $K_p$-listing, for all $p$, is the same in both the CONGEST and CONGESTED CLIQUE models, at $tilde{Theta}(n^{1 - 2/p})$ rounds. For $p=4$, our result additionally matches the $tilde{Omega}(n^{1/2})$ lower bound for $K_4$-emph{detection} by Czumaj and Konrad [DISC 2018], implying that the round complexities for detection and listing of $K_4$ are equivalent in the CONGEST model. |
| キーワード(和) | 分散計算 / 分散アルゴリズム / グラフ問題 / クリーク |
| キーワード(英) | Distributed computing / Distributed algorithms / Graph problems / Cliques |
| 資料番号 | COMP2020-31 |
| 発行日 | 2021-03-01 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2021/3/8(から1日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 増澤 利光(阪大) |
| 委員長氏名（英） | Toshimitsu Masuzawa(Osaka Univ.) |
| 副委員長氏名（和） | 小野 廣隆(名大) |
| 副委員長氏名（英） | Hirotaka Ono(Nagoya Univ) |
| 幹事氏名（和） | 大下 福仁(奈良先端大) / 安藤 映(専修大) |
| 幹事氏名（英） | Fukuhito Ooshita(NAIST) / Ei Ando(Senshu Univ.) |
| 幹事補佐氏名（和） | 大舘 陽太(名大) |
| 幹事補佐氏名（英） | Yota Otachi(Nagoya Univ) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | [Invited Talk] Tight Distributed Listing of Cliques |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散計算 / Distributed computing |
| キーワード(2)（和/英） | 分散アルゴリズム / Distributed algorithms |
| キーワード(3)（和/英） | グラフ問題 / Graph problems |
| キーワード(4)（和/英） | クリーク / Cliques |
| 第 1 著者 氏名（和/英） | Keren Censor-Hillel / Keren Censor-Hillel |
| 第 1 著者 所属（和/英） | Technion(略称：Technion) Technion(略称：Technion) |
| 第 2 著者 氏名（和/英） | Yi-Jun Chang / Yi-Jun Chang |
| 第 2 著者 所属（和/英） | ETH(略称：ETH) ETH(略称：ETH) |
| 第 3 著者 氏名（和/英） | Fran?ois Le Gall / Fran?ois Le Gall |
| 第 3 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 第 4 著者 氏名（和/英） | Dean Leitersdorf / Dean Leitersdorf |
| 第 4 著者 所属（和/英） | Technion(略称：Technion) Technion(略称：Technion) |
| 発表年月日 | 2021-03-08 |
| 資料番号 | COMP2020-31 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | COMP-426 |
| ページ範囲 | pp.24-24(COMP), |
| ページ数 | 1 |
| 発行日 | 2021-03-01 (COMP) |