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.2021.49
URN: urn:nbn:de:0030-drops-141187
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14118/
Chekuri, Chandra ;
Quanrud, Kent
Faster Algorithms for Rooted Connectivity in Directed Graphs
Abstract
We consider the fundamental problems of determining the rooted and global edge and vertex connectivities (and computing the corresponding cuts) in directed graphs. For rooted (and hence also global) edge connectivity with small integer capacities we give a new randomized Monte Carlo algorithm that runs in time Õ(n²). For rooted edge connectivity this is the first algorithm to improve on the Ω(n³) time bound in the dense-graph high-connectivity regime. Our result relies on a simple combination of sampling coupled with sparsification that appears new, and could lead to further tradeoffs for directed graph connectivity problems.
We extend the edge connectivity ideas to rooted and global vertex connectivity in directed graphs. We obtain a (1+ε)-approximation for rooted vertex connectivity in Õ(nW/ε) time where W is the total vertex weight (assuming integral vertex weights); in particular this yields an Õ(n²/ε) time randomized algorithm for unweighted graphs. This translates to a Õ(KnW) time exact algorithm where K is the rooted connectivity. We build on this to obtain similar bounds for global vertex connectivity.
Our results complement the known results for these problems in the low connectivity regime due to work of Gabow [Harold N. Gabow, 1995] for edge connectivity from 1991, and the very recent work of Nanongkai et al. [Nanongkai et al., 2019] and Forster et al. [Sebastian Forster et al., 2020] for vertex connectivity.
BibTeX - Entry
@InProceedings{chekuri_et_al:LIPIcs.ICALP.2021.49,
author = {Chekuri, Chandra and Quanrud, Kent},
title = {{Faster Algorithms for Rooted Connectivity in Directed Graphs}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {49:1--49:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14118},
URN = {urn:nbn:de:0030-drops-141187},
doi = {10.4230/LIPIcs.ICALP.2021.49},
annote = {Keywords: rooted connectivity, directed graph, fast algorithm, sparsification}
}
|
Keywords: |
|
rooted connectivity, directed graph, fast algorithm, sparsification |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
