Data Structures for Node Connectivity Queries

Author Zeev Nutov



PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.82.pdf
  • Filesize: 0.79 MB
  • 12 pages

Document Identifiers

Author Details

Zeev Nutov
  • The Open University of Israel, Ra'anana, Israel

Cite AsGet BibTex

Zeev Nutov. Data Structures for Node Connectivity Queries. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 82:1-82:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.82

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • node connectivity
  • minimum cuts
  • data structure
  • connectivity queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. C. Chekuri, T. Rukkanchanunt, and C. Xu. On element-connectivity preserving graph simplification. In 23rd European Symposium on Algorithms (ESA), pages 313-324, 2015. Google Scholar
  2. J. Chuzhoy and S. Khanna. An O(k³log n)-approximation algorithm for vertex-connectivity survivable network design. Theory of Computing, 8(1):401-413, 2012. Google Scholar
  3. R. F. Cohen, G. Di Battista, A. Kanevsky, and R. Tamassia. Reinventing the wheel: an optimal data structure for connectivity queries. In 25th Symposium on Theory of Computing (STOC), pages 194-200, 1993. Google Scholar
  4. P. Erdös and A. Hajnal. On chromatic number of graphs and set-systems. Acta Mathematica Hungarica, 17(1–2):61-99, 1966. Google Scholar
  5. R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9, 1961. Google Scholar
  6. J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J. Computing, 2(3):135-158, 1973. Google Scholar
  7. T-H. Hsu and H-I. Lu. An optimal labeling for node connectivity. In 20th International Symposium Algorithms and Computation (ISAAC), pages 303-310, 2009. Google Scholar
  8. R. Izsak and Z. Nutov. A note on labeling schemes for graph connectivity. Information Processing Letters, 112(1-2):39-43, 2012. Google Scholar
  9. A. Kanevsky, R. Tamassia, G. Di Battista, and J. Chen. On-line maintenance of the four-connected components of a graph. In 32nd Annual Symposium on Foundations of Computer Science (FOCS), pages 793-801, 1991. Google Scholar
  10. M. Katz, N. A. Katz, A. Korman, and D. Peleg. Labeling schemes for flow and connectivity. SIAM J. Comput., 34(1):23-40, 2004. Google Scholar
  11. A. Korman. Labeling schemes for vertex connectivity. ACM Transactions on Algorithms, 6(2), 2010. Google Scholar
  12. W. Mader. Ecken vom grad n in minimalen n-fach zusammenhängenden graphen. Archive der Mathematik, 23:219-224, 1972. Google Scholar
  13. D. W. Matula and L. L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417-427, 1983. Google Scholar
  14. H. Nagamochi and T. Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(5&6):583-596, 1992. Google Scholar
  15. Z. Nutov. Approximating subset k-connectivity problems. J. Discrete Algorithms, 17:51-59, 2012. Google Scholar
  16. Z. Nutov. Improved approximation algorithms for minimum cost node-connectivity augmentation problems. Theory of Computing Systems, 62(3):510-532, 2018. Google Scholar
  17. S. Pettie, T. Saranurak, and L. Yin. Optimal vertex connectivity oracles. In 54th Symposium on Theory of Computing (STOC), pages 151-161, 2022. Google Scholar
  18. S. Pettie and L. Yin. The structure of minimum vertex cuts. In 48th International Colloquium on Automata, Languages, and Programming (ICALP), pages 105:1-105:20, 2021. Google Scholar
  19. A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer Verlag, Berlin Heidelberg, 2003. Google Scholar
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