A Distributed Conductance Tester Without Global Information Collection

Tugkan Batu, Amitabh Trehan, Chhaya Trehan

We propose a simple and time-optimal algorithm for property testing a graph for its conductance in the CONGEST model. Our algorithm takes only $O(\log n)$ rounds of communication (…