Fast edge orientation for unweighted graphs

ABSTRACT

We consider an unweighted undirected graph with n vertices, m edges, and edge-connectivity 2k. The weak edge orientation problem requires that the edges of this graph be oriented so the resulting directed graph is at least k edge-connected. Nash-Williams proved the existence of such orientations and subsequently Frank [6], Gabow [7], and Nagamochi-Ibaraki [12] gave algorithmic constructions. All of these algorithms took time at least quadratic in n. We provide the first sub-quadratic (in n) algorithm for this problem. Our algorithm takes Õ(nk⁴ + m) time. This improves the previous best bounds of Õ(n²k² + m) by Gabow [7] and Õ(n²m) by Nagamochi-Ibaraki [12] when k ≤ √n. Indeed, many real networks have k ≪ n.

Our algorithm uses the fast edge splitting paradigm introduced by Bhalgat et al. [2]. We seek to split out a large fraction of the vertices, recurse on the resulting graph, and then put back the split-off vertices. The main challenge we face is that only vertices with even degree may be split-off in an undirected graph and there may not be any such vertex in the current graph. The edge orientation algorithms of Gabow and Nagamochi-Ibaraki as well as Frank's proof are based on showing the existence of at least two even degree vertices (in fact, vertices with degree 2k) in a 2k minimally connected graph. We generalize this to show that in any edge minimal 2k edge-connected graph, there are at least n/3 even degree vertices. These vertices are then split-off.

Our next challenge is to drop edges from the given graph so it remains 2k connected and yet has Ω(n) even degree vertices. We provide an algorithm that discards edges specifically to produce Ω(n) even degree vertices while maintaining connectivity 2k and takes time Õ(nk⁴ + m). Note that this algorithm does not necessarily make the graph edge-minimally 2k edge-connected. We also briefly outline an Õ(nk⁵ + m) time algorithm that achieves edge-minimality which improves the previous best bound of Õ(m + n²k²) by Gabow [7].

REFERENCES

• 1: Ramesh Hariharan , Telikepalli Kavitha , Debmalya Panigrahi , Anand Bhalgat, An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250879]
• 2: Anand Bhalgat , Ramesh Hariharan , Telikepalli Kavitha , Debmalya Panigrahi, Fast edge splitting and Edmonds' arborescence construction for unweighted graphs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.455-464, January 20-22, 2008, San Francisco, California
• 3: Richard Cole , Ramesh Hariharan, A fast algorithm for computing steiner edge connectivity, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780568]
• 4: E. A. Dinits, A. V. Karzanov, M. V. Lomonosov. On the structure of a family of minimal weighted cuts in a graph. Studies in Discrete Optimization, A. A. Fridman, Ed., pp. 240--306, 1976. (Original article in Russian, translation available from National Translation Center, Library of Congress, Cataloging Distribution Center, Washington D.C, 20541 (NTC 89-20265)).
• 5: J. Edmonds, Submodular functions, matroids, and certain polyhedra, Calgary International Conf. on Combinatorial Structures and their Applications, Gordon and Breach, New York, pp. 69--87, 1969.
• 6: András Frank, Applications of submodular functions, Surveys in combinatorics, 1993, Cambridge University Press, New York, NY, 1993
• 7: Harold N. Gabow, Efficient splitting off algorithms for graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.696-705, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195436]
• 8: R. E. Gomory and T. C. Hu. Multi-terminal network flows, J. Soc. Indust. Appl. Math. 9(4), pp. 551--570, 1961.
• 9: L. Lovász, Lecture, Conference of Graph Theory, Prague, 1974.
• 10: L. Lovász, Combinatorial Problems and Exercises, 2nd Ed., North-Holland, New York, 1993.
• 11: Hiroshi Nagamochi and Toshihide Ibaraki, A linear-time algorithm for finding a sparse k-cormected spanning subgraph of a k-connected graph, Algorithmica, 7, 1992, pp. 583596.
• 12: Hiroshi Nagamochi , Toshihide Ibaraki, Deterministic Õ(nm) time edge-splitting in undirected graphs, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.64-73, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237830]
• 13: C. St. J. A. Nash-Williams,On orientations, connectivity and odd vertex pairings in finite graphs, Canadian. J. Math., 12, 1960, pp. 555--567.
• 14: W. Mader, A reduction method for edge connectivity in graphs, Ann. Discrete Math., 9, 1978, pp. 145--164.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms