A Cut Tree Representation for Pendant Pairs

Authors On-Hei S. Lo, Jens M. Schmidt



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.38.pdf
  • Filesize: 424 kB
  • 9 pages

Document Identifiers

Author Details

On-Hei S. Lo
  • Institut für Mathematik, Technische Universität Ilmenau, Weimarer Strasse 25, D-98693 Ilmenau, Germany
Jens M. Schmidt
  • Institut für Mathematik, Technische Universität Ilmenau, Weimarer Strasse 25, D-98693 Ilmenau, Germany

Cite AsGet BibTex

On-Hei S. Lo and Jens M. Schmidt. A Cut Tree Representation for Pendant Pairs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 38:1-38:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.38

Abstract

Two vertices v and w of a graph G are called a pendant pair if the maximal number of edge-disjoint paths in G between them is precisely min{d(v),d(w)}, where d denotes the degree function. The importance of pendant pairs stems from the fact that they are the key ingredient in one of the simplest and most widely used algorithms for the minimum cut problem today. Mader showed 1974 that every simple graph with minimum degree delta contains Omega(delta^2) pendant pairs; this is the best bound known so far. We improve this result by showing that every simple graph G with minimum degree delta >= 5 or with edge-connectivity lambda >= 4 or with vertex-connectivity kappa >= 3 contains in fact Omega(delta |V|) pendant pairs. We prove that this bound is tight from several perspectives, and that Omega(delta |V|) pendant pairs can be computed efficiently, namely in linear time when a Gomory-Hu tree is given. Our method utilizes a new cut tree representation of graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Mathematics of computing → Graph algorithms
Keywords
  • Pendant Pairs
  • Pendant Tree
  • Maximal Adjacency Ordering
  • Maximum Cardinality Search
  • Testing Edge-Connectivity
  • Gomory-Hu Tree

Metrics

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

References

  1. A. Bhalgat, R. Hariharan, T. Kavitha, and D. Panigrahi. An Õ(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs. In Proceedings of the 39th Annual Symposium on Theory of Computing (STOC'07), pages 605-614, 2007. URL: http://dx.doi.org/10.1145/1250790.1250879.
  2. E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation. Soviet Math Doklady, 11:1277-1280, 1970. Google Scholar
  3. A. Frank. On the edge-connectivity algorithm of Nagamochi and Ibaraki. Laboratoire Artemis, IMAG, Université J. Fourier, Grenoble, March 1994. Google Scholar
  4. M. Henzinger, S. Rao, and D. Wang. Local Flow Partitioning for Faster Edge Connectivity. In Proceedings of the 28th Annual Symposium on Discrete Algorithms (SODA'17), pages 1919-1938, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.125.
  5. A. V. Karzanov. On finding a maximum flow in a network with special structure and some applications. Matematicheskie Voprosy Upravleniya Proizvodstvom (in Russian), pages 81-94, 1973. Google Scholar
  6. K. Kawarabayashi and M. Thorup. Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time. In Proceedings of the 47th Annual Symposium on Theory of Computing (STOC'15), pages 665-674, 2015. URL: http://dx.doi.org/10.1145/2746539.2746588.
  7. W. Mader. Existenz gewisser Konfigurationen in n-gesättigten Graphen und in Graphen genügend großer Kantendichte. Mathematische Annalen, 194:295-312, 1971. Google Scholar
  8. W. Mader. Grad und lokaler Zusammenhang in endlichen Graphen. Mathematische Annalen, 205:9-11, 1973. Google Scholar
  9. W. Mader. Kantendisjunkte Wege in Graphen. Monatshefte für Mathematik, 78(5):395-404, 1974. Google Scholar
  10. W. Mader. On vertices of degree n in minimally n-connected graphs and digraphs. Bolyai Society Mathematical Studies (Combinatorics, Paul Erdős is Eighty, Keszthely, 1993), 2:423-449, 1996. Google Scholar
  11. H. Nagamochi and T. Ibaraki. Computing Edge-Connectivity in Multigraphs and Capacitated Graphs. SIAM Journal on Discrete Mathematics, 5(1):54-66, 1992. Google Scholar
  12. M. Stoer and F. Wagner. A simple min-cut algorithm. Journal of the ACM, 44(4):585-591, 1997. Google Scholar
  13. R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13(3):566-579, 1984. 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