Distributed minimum cut approximation

DOI10.1007/978-3-642-41527-2_1MaRDI QIDQ2920962zbMATH OpenOpenAlexFDO

Authors Mohsen Ghaffari, Fabian Kuhn

Publication date 29 September 2014

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

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(24)

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

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)