License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.82
URN: urn:nbn:de:0030-drops-164230
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16423/
Go to the corresponding LIPIcs Volume Portal

Kogan, Shimon ; Parter, Merav

Beating Matrix Multiplication for n^{1/3}-Directed Shortcuts

pdf-format:
LIPIcs-ICALP-2022-82.pdf (1.0 MB)

Abstract

For an n-vertex digraph G = (V,E) and integer parameter D, a D-shortcut is a small set H of directed edges taken from the transitive closure of G, satisfying that the diameter of G ∪ H is at most D. A recent work [Kogan and Parter, SODA 2022] presented shortcutting algorithms with improved diameter vs. size tradeoffs. Most notably, obtaining linear size D-shortcuts for D = Õ(n^{1/3}), breaking the √n-diameter barrier. These algorithms run in O(n^{ω}) time, as they are based on the computation of the transitive closure of the graph.
We present a new algorithmic approach for D-shortcuts, that matches the bounds of [Kogan and Parter, SODA 2022], while running in o(n^{ω}) time for every D ≥ n^{1/3}. Our approach is based on a reduction to the min-cost max-flow problem, which can be solved in Õ(m+n^{3/2}) time due to the recent breakthrough result of [Brand et al., STOC 2021].
We also demonstrate the applicability of our techniques to computing the minimal chain covers and dipath decompositions for directed acyclic graphs. For an n-vertex m-edge digraph G = (V,E), our key results are:
- An Õ(n^{1/3}⋅ m+n^{3/2})-time algorithm for computing D-shortcuts of linear size for D = Õ(n^{1/3}), and an Õ(n^{1/4}⋅ m+n^{7/4})-time algorithm for computing D-shortcuts of Õ(n^{3/4}) edges for D = Õ(n^{1/2}).
- For a DAG G, we provide Õ(m+n^{3/2})-time algorithms for computing its minimum chain covers, maximum antichain, and decomposition into dipaths and independent sets. This improves considerably over the state-of-the-art bounds by [Caceres et al., SODA 2022] and [Grandoni et al., SODA 2021].
Our results also provide a new connection between shortcutting sets and the seemingly less related problems of minimum chain covers and the maximum antichains in DAGs.

BibTeX - Entry

@InProceedings{kogan_et_al:LIPIcs.ICALP.2022.82,
  author =	{Kogan, Shimon and Parter, Merav},
  title =	{{Beating Matrix Multiplication for n^\{1/3\}-Directed Shortcuts}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{82:1--82:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16423},
  URN =		{urn:nbn:de:0030-drops-164230},
  doi =		{10.4230/LIPIcs.ICALP.2022.82},
  annote =	{Keywords: Directed Shortcuts, Transitive Closure, Width}
}

Keywords: Directed Shortcuts, Transitive Closure, Width
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI