Distributed minimum cut approximation

DOI10.1007/978-3-642-41527-2_1zbMATH Open1435.68379arXiv1305.5520OpenAlexW1497938971MaRDI QIDQ2920962FDOQ2920962

Authors: Mohsen Ghaffari, Fabian Kuhn 

Publication date: 29 September 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We study the problem of computing approximate minimum edge cuts by distributed algorithms. We use a standard synchronous message passing model where in each round, $O(logn)$ bits can be transmitted over each edge (a.k.a. the CONGEST model). We present a distributed algorithm that, for any weighted graph and any $epsilonin(0,1)$, with high probability finds a cut of size at most $O(epsilo{n}^{-1}lambda)$ in $O(D)+ildeO(n^{1/2+epsilon})$ rounds, where $lambda$ is the size of the minimum cut. This algorithm is based on a simple approach for analyzing random edge sampling, which we call the random layering technique. In addition, we also present another distributed algorithm, which is based on a centralized algorithm due to Matula [SODA '93], that with high probability computes a cut of size at most $(2+epsilon)lambda$ in $ildeO((D+sqrtn)/epsilo{n}^5)$ rounds for any $epsilon>0$. The time complexities of both of these algorithms almost match the $ildeOmega(D+sqrtn)$ lower bound of Das Sarma et al. [STOC '11], thus leading to an answer to an open question raised by Elkin [SIGACT-News '04] and Das Sarma et al. [STOC '11]. Furthermore, we also strengthen the lower bound of Das Sarma et al. by extending it to unweighted graphs. We show that the same lower bound also holds for unweighted multigraphs (or equivalently for weighted graphs in which $O(wlogn)$ bits can be transmitted in each round over an edge of weight $w$), even if the diameter is $D=O(logn)$. For unweighted simple graphs, we show that even for networks of diameter $ildeO(frac1lambdacdotsqrtfracnalphalambda)$, finding an $alpha$-approximate minimum cut in networks of edge connectivity $lambda$ or computing an $alpha$-approximation of the edge connectivity requires $ildeOmega(D+sqrtfracnalphalambda)$ rounds.

Full work available at URL: https://arxiv.org/abs/1305.5520

Recommendations

• Almost-Tight Distributed Minimum Cut Algorithms
• Congested Clique Algorithms for the Minimum Cut Problem
• Distributed sparse cut approximation
• Connectivity and minimum cut approximation in the broadcast congested clique
• Fast Distributed Computation of Cuts Via Random Circulations

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Approximation algorithms (68W25) Distributed algorithms (68W15)

Cited In (19)

• Fast Distributed Approximation for Max-Cut
• A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
• Near-optimal distributed maximum flow
• Small cuts and connectivity certificates: a fault tolerant approach
• Distributed sparse cut approximation
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Message lower bounds via efficient network synchronization
• The hardness of optimization problems on the weighted massively parallel computation model
• Near-optimal distributed maximum flow (extended abstract)
• Low-congestion shortcuts without embedding
• Almost-Tight Distributed Minimum Cut Algorithms
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• On efficient distributed construction of near optimal routing schemes
• An efficient distributed thinning algorithm
• Distributed graph algorithms and their complexity: an introduction
• Finding a small vertex cut on distributed networks
• Distributed MST and broadcast with fewer messages, and faster gossiping
• Time-message trade-offs in distributed algorithms
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

This page was built for publication: Distributed minimum cut approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920962)