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.ESA.2022.82
URN: urn:nbn:de:0030-drops-170205
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17020/
Go to the corresponding LIPIcs Volume Portal

Nutov, Zeev

Data Structures for Node Connectivity Queries

pdf-format:
LIPIcs-ESA-2022-82.pdf (0.8 MB)

Abstract

Let κ(s,t) denote the maximum number of internally disjoint st-paths in an undirected graph G. We consider designing a data structure that includes a list of cuts, and answers the following query: given s,t ∈ V, determine whether κ(s,t) ≤ k, and if so, return a pointer to an st-cut of size ≤ k (or to a minimum st-cut) in the list. A trivial data structure that includes a list of n(n-1)/2 cuts and requires Θ(kn²) space can answer each query in O(1) time. We obtain the following results.
- In the case when G is k-connected, we show that 2n cuts suffice, and that these cuts can be partitioned into 2k+1 laminar families. Thus using space O(kn) we can answers each min-cut query in O(1) time, slightly improving and substantially simplifying the proof of a recent result of Pettie and Yin [S. Pettie and L. Yin, 2021]. We then extend this data structure to subset k-connectivity.
- In the general case we show that (2k+1)n cuts suffice to return an st-cut of size ≤ k, and a list of size k(k+2)n contains a minimum st-cut for every s,t ∈ V. Combining our subset k-connectivity data structure with the data structure of Hsu and Lu [T-H. Hsu and H-I. Lu, 2009] for checking k-connectivity, we give an O(k² n) space data structure that returns an st-cut of size ≤ k in O(log k) time, while O(k³ n) space enables to return a minimum st-cut.

BibTeX - Entry

@InProceedings{nutov:LIPIcs.ESA.2022.82,
  author =	{Nutov, Zeev},
  title =	{{Data Structures for Node Connectivity Queries}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{82:1--82:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17020},
  URN =		{urn:nbn:de:0030-drops-170205},
  doi =		{10.4230/LIPIcs.ESA.2022.82},
  annote =	{Keywords: node connectivity, minimum cuts, data structure, connectivity queries}
}

Keywords: node connectivity, minimum cuts, data structure, connectivity queries
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

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