2014/02/11 by Hirvonen, Juho, Rybicki, Joel, Schmid, Stefan +1 · 2 citations
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1402.2543
We study the problem of finding large cuts in d-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size (1/2 + 0.177/√(d))m, where m is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size (1/2 + 0.28125/√(d))m. As a corollary, this shows that in any d-regular triangle-free graph there exists a cut of at least this size. Our algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying computational techniques in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of d.