Low congestion cycle covers and their applications

DOI10.1137/1.9781611975482.101MaRDI QIDQ5236285zbMATH OpenOpenAlexFDO

Authors Eylon Yogev, M. Parter

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Abstract: A cycle cover of a bridgeless graph $G$ is a collection of simple cycles in $G$ such that each edge $e$ appears on at least one cycle. The common objective in cycle cover computation is to minimize the total lengths of all cycles. Motivated by applications to distributed computation, we introduce the notion of emph{low-congestion} cycle covers, in which all cycles in the cycle collection are both emph{short} and nearly emph{edge-disjoint}. Formally, a $(d,c)$-cycle cover of a graph $G$ is a collection of cycles in $G$ in which each cycle is of length at most $d$ and each edge participates in at least one cycle and at most $c$ cycles. A-priori, it is not clear that cycle covers that enjoy both a small overlap and a short cycle length even exist, nor if it is possible to efficiently find them. Perhaps quite surprisingly, we prove the following: Every bridgeless graph of diameter $D$ admits a $(d,c)$-cycle cover where $d=ildeO(D)$ and $c=ildeO(1)$. These parameters are existentially tight up to polylogarithmic terms. Furthermore, we show how to extend our result to achieve universally optimal cycle covers. Let $C_e$ is the length of the shortest cycle that covers $e$, and let $OPT(G)=ma{x}_{einG}{C}_e$. We show that every bridgeless graph admits a $(d,c)$-cycle cover where $d=ildeO(OPT(G))$ and $c=ildeO(1)$. We demonstrate the usefulness of low congestion cycle covers in different settings of resilient computation. For instance, we consider a Byzantine fault model where in each round, the adversary chooses a single message and corrupt in an arbitrarily manner. We provide a compiler that turns any $r$-round distributed algorithm for a graph $G$ with diameter $D$, into an equivalent fault tolerant algorithm with $rcdotpoly(D)$ rounds.

Recommendations

• scientific article; zbMATH DE number 1555925
• Cycle covering in bridgeless graphs
• Covering Graphs by Cycles
• Short cycle covers of graphs with at most 77\% vertices of degree two
• Short cycle covers of graphs with minimum degree three

Cited in

(6)

• Low-congestion shortcuts without embedding
• scientific article; zbMATH DE number 1555925 (Why is no real title available?)
• Distributed CONGEST Algorithms against Mobile Adversaries
• On packing low-diameter spanning trees
• Deterministic replacement path covering
• Invited talk: Resilient distributed algorithms

This page was built for publication: Low congestion cycle covers and their applications

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