Local Approximation of the Maximum Cut in Regular Graphs

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least 1 2 in average. When the graph is d-regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MAXCUT in regular graphs. We first prove that if G is d-regular, with d even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of 1/d for d-regular graphs with d odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio 1/d + epsilon (with epsilon > 0) can run in a constant number of rounds. We also prove results of a similar flavour for the MAXDI-CUT problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut.