On the multiparty communication complexity of testing triangle-freeness

DOI10.1145/3087801.3087821MaRDI QIDQ5368951zbMATH OpenOpenAlexFDO

Authors Orr Fischer, Shay Gershtein, Rotem Oshman

Publication date 11 October 2017

Published in Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.08438

zbMATH Keywords

communication complexityproperty testingtriangle-freeness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Abstract: In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party communication complexity, focusing on testing triangle-freeness in graphs. We consider the $extitcoordinator$ model, where we have $k$ players receiving private inputs, and a coordinator who receives no input; the coordinator can communicate with all the players, but the players cannot communicate with each other. In this model, we ask: if an input graph is divided between the players, with each player receiving some of the edges, how many bits do the players and the coordinator need to exchange to determine if the graph is triangle-free, or $extitfar$ from triangle-free? For general communication protocols, we show that $ildeO(k(nd{)}^{1/4}+k^2)$ bits are sufficient to test triangle-freeness in graphs of size $n$ with average degree $d$ (the degree need not be known in advance). For $extitsimultaneous$ protocols, where there is only one communication round, we give a protocol that uses $ildeO(ksqrtn)$ bits when $d=O(sqrtn)$ and $ildeO(k(nd{)}^{1/3})$ when $d=Omega(sqrtn)$; here, again, the average degree $d$ does not need to be known in advance. We show that for average degree $d=O(1)$, our simultaneous protocol is asymptotically optimal up to logarithmic factors. For higher degrees, we are not able to give lower bounds on testing triangle-freeness, but we give evidence that the problem is hard by showing that finding an edge that participates in a triangle is hard, even when promised that at least a constant fraction of the edges must be removed in order to make the graph triangle-free.

Recommendations

• Testing Triangle-Freeness in General Graphs
• Multiparty quantum communication complexity of triangle finding
• The communication complexity of set intersection and multiple equality testing
• Three notes on distributed property testing

Cited in

(5)

• Property testing of planarity in the \textsf{CONGEST} model
• scientific article; zbMATH DE number 1870232 (Why is no real title available?)
• The communication complexity of set intersection and multiple equality testing
• The communication complexity of set intersection and multiple equality testing
• Distributed Testing of Graph Isomorphism in the CONGEST Model.

This page was built for publication: On the multiparty communication complexity of testing triangle-freeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368951)