Low-Congestion Shortcut and Graph Parameters
2019
Distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity lower bound of $${\tilde{\Omega }}(\sqrt{n} + D)$$
rounds for several global problems, where n denotes the number of nodes and D the diameter of the input graph. Because such a lower bound is derived from special “hard-core” instances, it does not necessarily apply to specific popular graph classes such as planar graphs. The concept of low-congestion shortcuts was initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologies. In particular, given a graph class $${\mathcal {C}}$$
, an f-round algorithm for constructing shortcuts of quality q for any instance in $${\mathcal {C}}$$
results in $${\tilde{O}}(q + f)$$
-round algorithms for solving several fundamental graph problems such as minimum spanning tree and minimum cut, for $${\mathcal {C}}$$
. The main interest on this line is to identify the graph classes allowing the shortcuts that are efficient in the sense of breaking $${\tilde{O}}(\sqrt{n}+D)$$
-round general lower bounds. In this study, we consider the relationship between the quality of low-congestion shortcuts and the following four major graph parameters: doubling dimension, chordality, diameter, and clique-width. The key ingredient of the upper-bound side is a novel shortcut construction technique known as short-hop extension, which might be of independent interest.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
3
Citations
NaN
KQI