Distributed Complexity of $P_k$-freeness: Decision and Certification
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929561420169216 |
|---|---|
| author | Miyamoto, Masayuki |
| author_facet | Miyamoto, Masayuki |
| contents | The class of graphs that do not contain a path on $k$ nodes as an induced subgraph ($P_k$-free graphs) has rich applications in the theory of graph algorithms. This paper explores the problem of deciding $P_k$-freeness from the viewpoint of distributed computing.
For specific small values of $k$, we present the \textit{first} $\mathsf{CONGEST}$ algorithms specified for $P_k$-freeness, utilizing structural properties of $P_k$-free graphs in a novel way. Specifically, we show that $P_k$-freeness can be decided in $\tilde{O}(1)$ rounds for $k=4$ in the $\mathsf{broadcast\;CONGEST}$ model, and in $\tilde{O}(n)$ rounds for $k=5$ in the $\mathsf{CONGEST}$ model, where $n$ is the number of nodes in the network and $\tilde{O}(\cdot)$ hides a $\mathrm{polylog}(n)$ factor. These results significantly improve the previous $O(n^{2-2/(3k+2)})$ upper bounds by Eden et al. (Dist.~Comp.~2022). We also construct a local certification of $P_5$-freeness with certificates of size $\tilde{O}(n)$. This is nearly optimal, given our $Ω(n^{1-o(1)})$ lower bound on certificate size, and marks a significant advancement as no nontrivial bounds for proof-labeling schemes of $P_5$-freeness were previously known.
For general $k$, we establish the first $\mathsf{CONGEST}$ lower bound, which is of the form $n^{2-1/Θ(k)}$. The $n^{1/Θ(k)}$ factor is unavoidable, in view of the $O(n^{2-2/(3k+2)})$ upper bound mentioned above. Additionally, our approach yields the \textit{first} superlinear lower bound on certificate size for local certification. This partially answers the conjecture on the optimal certificate size of $P_k$-freeness, asked by Bousquet et al. (arXiv:2402.12148).
Finally, we propose a novel variant of the problem called ordered $P_k$ detection, and show a linear lower bound and its nontrivial connection to distributed subgraph detection. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_20353 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distributed Complexity of $P_k$-freeness: Decision and Certification Miyamoto, Masayuki Distributed, Parallel, and Cluster Computing The class of graphs that do not contain a path on $k$ nodes as an induced subgraph ($P_k$-free graphs) has rich applications in the theory of graph algorithms. This paper explores the problem of deciding $P_k$-freeness from the viewpoint of distributed computing. For specific small values of $k$, we present the \textit{first} $\mathsf{CONGEST}$ algorithms specified for $P_k$-freeness, utilizing structural properties of $P_k$-free graphs in a novel way. Specifically, we show that $P_k$-freeness can be decided in $\tilde{O}(1)$ rounds for $k=4$ in the $\mathsf{broadcast\;CONGEST}$ model, and in $\tilde{O}(n)$ rounds for $k=5$ in the $\mathsf{CONGEST}$ model, where $n$ is the number of nodes in the network and $\tilde{O}(\cdot)$ hides a $\mathrm{polylog}(n)$ factor. These results significantly improve the previous $O(n^{2-2/(3k+2)})$ upper bounds by Eden et al. (Dist.~Comp.~2022). We also construct a local certification of $P_5$-freeness with certificates of size $\tilde{O}(n)$. This is nearly optimal, given our $Ω(n^{1-o(1)})$ lower bound on certificate size, and marks a significant advancement as no nontrivial bounds for proof-labeling schemes of $P_5$-freeness were previously known. For general $k$, we establish the first $\mathsf{CONGEST}$ lower bound, which is of the form $n^{2-1/Θ(k)}$. The $n^{1/Θ(k)}$ factor is unavoidable, in view of the $O(n^{2-2/(3k+2)})$ upper bound mentioned above. Additionally, our approach yields the \textit{first} superlinear lower bound on certificate size for local certification. This partially answers the conjecture on the optimal certificate size of $P_k$-freeness, asked by Bousquet et al. (arXiv:2402.12148). Finally, we propose a novel variant of the problem called ordered $P_k$ detection, and show a linear lower bound and its nontrivial connection to distributed subgraph detection. |
| title | Distributed Complexity of $P_k$-freeness: Decision and Certification |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2410.20353 |