Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Local approximation of the Maximum Cut in regular graphs
 
research article

Local approximation of the Maximum Cut in regular graphs

Bamas, Etienne  
•
Esperet, Louis
June 8, 2020
Theoretical Computer Science

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) 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 expectation. 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 when d is 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 flavor for the MAXDICUT 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. (C) 2020 Elsevier B.V. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.tcs.2020.03.008
Web of Science ID

WOS:000526405200004

Author(s)
Bamas, Etienne  
Esperet, Louis
Date Issued

2020-06-08

Publisher

ELSEVIER

Published in
Theoretical Computer Science
Volume

820

Start page

45

End page

59

Subjects

Computer Science, Theory & Methods

•

Computer Science

•

maximum cut

•

approximation algorithm

•

distributed algorithm

•

regular graphs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Available on Infoscience
May 21, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/168858
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés