Large cuts with local algorithms on triangle-free graphs (Q2411507)

Summary: Let \(G\) be a \(d\)-regular triangle-free graph with \(m\) edges. We present an algorithm which finds a cut in \(G\) with at least \((1/2 + 0.28125/\sqrt{d})m\) edges in expectation, improving upon Shearer's classic result. In particular, this implies that any \(d\)-regular triangle-free graph has a cut of at least this size, and thus, we obtain a new lower bound for the maximum number of edges in a bipartite subgraph of \(G\). Our algorithm is simpler than Shearer's classic algorithm and it can be interpreted as a very efficient \textit{randomised distributed (local) algorithm}: each node needs to produce only one random bit, and the algorithm runs in one round. The randomised algorithm itself was discovered using \textit{computational techniques}. We show that for any fixed \(d\), there exists a weighted neighbourhood graph \(\mathcal{N}_d\) such that there is a one-to-one correspondence between heavy cuts of \(\mathcal{N}_d\) and randomised local algorithms that find large cuts in any \(d\)-regular input graph. This turns out to be a useful tool for analysing the existence of cuts in \(d\)-regular graphs: we can compute the optimal cut of \(\mathcal{N}_d\) to attain a lower bound on the maximum cut size of any \(d\)-regular triangle-free graph.