Bamas, EtienneEsperet, Louis2020-08-262020-08-262020-08-262019-01-0110.1007/978-3-030-30786-8_6https://infoscience.epfl.ch/handle/20.500.14299/171133WOS:000557920500006This 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.Computer Science, Theory & MethodsMathematics, AppliedComputer ScienceMathematicsmaximum cutdistributed approximationlocal algorithmmax-cuttext::conference output::conference proceedings::conference paper