Kitamura, Naoki ;
Kitagawa, Hirotaka ;
Otachi, Yota ;
Izumi, Taisuke
LowCongestion Shortcut and Graph Parameters
Abstract
Distributed graph algorithms in the standard CONGEST model often exhibit the timecomplexity lower bound of Omega~(sqrt{n} + D) rounds for many global problems, where n is the number of nodes and D is the diameter of the input graph. Since such a lower bound is derived from special "hardcore" instances, it does not necessarily apply to specific popular graph classes such as planar graphs. The concept of lowcongestion shortcuts is initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologies. Specifically, given a specific graph class X, an fround algorithm of constructing shortcuts of quality q for any instance in X results in O~(q + f)round algorithms of solving several fundamental graph problems such as minimum spanning tree and minimum cut, for X. The main interest on this line is to identify the graph classes allowing the shortcuts which are efficient in the sense of breaking O~(sqrt{n}+D)round general lower bounds.
In this paper, we consider the relationship between the quality of lowcongestion shortcuts and three major graph parameters, chordality, diameter, and cliquewidth. The main contribution of the paper is threefold: (1) We show an O(1)round algorithm which constructs a lowcongestion shortcut with quality O(kD) for any kchordal graph, and prove that the quality and running time of this construction is nearly optimal up to polylogarithmic factors. (2) We present two algorithms, each of which constructs a lowcongestion shortcut with quality O~(n^{1/4}) in O~(n^{1/4}) rounds for graphs of D=3, and that with quality O~(n^{1/3}) in O~(n^{1/3}) rounds for graphs of D=4 respectively. These results obviously deduce two MST algorithms running in O~(n^{1/4}) and O~(n^{1/3}) rounds for D=3 and 4 respectively, which almost close the longstanding complexity gap of the MST construction in smalldiameter graphs originally posed by Lotker et al. [Distributed Computing 2006]. (3) We show that bounding cliquewidth does not help the construction of good shortcuts by presenting a network topology of cliquewidth six where the construction of MST is as expensive as the general case.
BibTeX  Entry
@InProceedings{kitamura_et_al:LIPIcs:2019:11332,
author = {Naoki Kitamura and Hirotaka Kitagawa and Yota Otachi and Taisuke Izumi},
title = {{LowCongestion Shortcut and Graph Parameters}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {25:125:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771269},
ISSN = {18688969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11332},
URN = {urn:nbn:de:0030drops113328},
doi = {10.4230/LIPIcs.DISC.2019.25},
annote = {Keywords: distributed graph algorithms, lowcongestion shortcut, kchordal graph, clique width, minimum spanning tree}
}
08.10.2019
Keywords: 

distributed graph algorithms, lowcongestion shortcut, kchordal graph, clique width, minimum spanning tree 
Seminar: 

33rd International Symposium on Distributed Computing (DISC 2019)

Issue date: 

2019 
Date of publication: 

08.10.2019 