Search Results

Documents authored by Kitagawa, Hirotaka


Document
Low-Congestion Shortcut and Graph Parameters

Authors: Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, and Taisuke Izumi

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


Abstract
Distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity 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 "hard-core" instances, it does not necessarily apply to specific popular graph classes such as planar graphs. The concept of low-congestion 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 f-round 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 low-congestion shortcuts and three major graph parameters, chordality, diameter, and clique-width. The main contribution of the paper is threefold: (1) We show an O(1)-round algorithm which constructs a low-congestion shortcut with quality O(kD) for any k-chordal 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 low-congestion 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 long-standing complexity gap of the MST construction in small-diameter graphs originally posed by Lotker et al. [Distributed Computing 2006]. (3) We show that bounding clique-width does not help the construction of good shortcuts by presenting a network topology of clique-width six where the construction of MST is as expensive as the general case.

Cite as

Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, and Taisuke Izumi. Low-Congestion Shortcut and Graph Parameters. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{kitamura_et_al:LIPIcs.DISC.2019.25,
  author =	{Kitamura, Naoki and Kitagawa, Hirotaka and Otachi, Yota and Izumi, Taisuke},
  title =	{{Low-Congestion Shortcut and Graph Parameters}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.25},
  URN =		{urn:nbn:de:0030-drops-113328},
  doi =		{10.4230/LIPIcs.DISC.2019.25},
  annote =	{Keywords: distributed graph algorithms, low-congestion shortcut, k-chordal graph, clique width, minimum spanning tree}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail