Primal-dual approach for directed vertex connectivity augmentation and generalizations

ABSTRACT

In their seminal paper, Frank and Jordán show that a large class of optimization problems including certain directed edge augmentation ones fall into the class of covering supermodular functions over pairs of sets. They also give an algorithm for such problems, however that relies on the ellipsoid method. Prior to our result, combinatorial algorithms existed only for the 0-1 valued problem. Our key result is a combinatorial algorithm for the general problem that includes directed vertex or S - T connectivity augmentation. The algorithm is based on the second author's previous algorithm for the 0-1 valued case.Our algorithm uses a primal-dual scheme for finding covers of partially ordered sets that satisfy natural abstract properties as in Frank and Jordán. For an initial (possibly greedy) cover the algorithm searches for witnesses for the necessity of each element in the cover. If no two (weighted) witnesses have a common cover, the solution is optimal. As long as this is not the case, the witnesses are gradually exchanged by smaller ones. Each witness change defines an appropriate change in the solution; these changes are finally unwound in a shortest path manner to obtain a solution of size one less.

REFERENCES

• 1: András A. Benczúr, Pushdown-reduce: an algorithm for connectivity augmentation and poset covering problems, Discrete Applied Mathematics, v.129 n.2-3, p.233-262, 01 August 2003 [doi>10.1016/S0166-218X(02)00570-X]
• 2: András A. Benczúr, Parallel and fast sequential algorithms for undirected edge connectivity augmentation, Math. Prog. B84(3):595--640 (1999) and Proc. 26th Annual ACM Symp. on Theory of Comp., pp. 658--667 (1994)
• 3: András A. Benczúr , David R. Karger, Augmenting undirected edge connectivity in Õ(n2) time, Journal of Algorithms, v.37 n.1, p.2-36, Oct. 2000 [doi>10.1006/jagm.2000.1093]
• 4: András A. Benczúr , Jörg Förster , Zoltán Király, Dilworth's Theorem and Its Application for Path Systems of a Cycle - Implementation and Analysis, Proceedings of the 7th Annual European Symposium on Algorithms, p.498-509, July 16-18, 1999
• 5: Cai, G-P. and Y-G. Sun, The minimum augmentation of any graph to a k-edge-connected graph, Networks19 (1989), pp. 151--172.
• 6: Frank, A., Combinatorial algorithms, algorithmic proofs. Doctoral Thesis, Budapest, Eötvös University (1976), in Hungarian
• 7: András Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM Journal on Discrete Mathematics, v.5 n.1, p.25-53, Feb. 1992 [doi>10.1137/0405003]
• 8: András Frank, Finding minimum generators of path systems, Journal of Combinatorial Theory Series B, v.75 n.2, p.237-244, March 1999 [doi>10.1006/jctb.1998.1877]
• 9: Frank, A., Finding minimum weighted generators of a path system, Contemporary Trends in Discrete Mathemaics (eds.: R. L. Graham, J. Kratochvil, J. Nesetril, and F. S. Roberts), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49 (1999), pp. 129--138.
• 10: Frank, A., Finding minimum edge-coverings of pairs of subsets, EGRES TECHNICAL REPORT SERIES (2001). Available at http://www.cs.elte.hu/egres/
• 11: András Frank , Tibor Jordán, Minimal edge-coverings of pairs of sets, Journal of Combinatorial Theory Series B, v.65 n.1, p.73-110, Sept. 1995 [doi>10.1006/jctb.1995.1044]
• 12: D S Franzblau , D J Kleitman, An algorithm for covering polygons with rectangles, Information and Control, v.63 n.3, p.164-189, Dec. 1986 [doi>10.1016/S0019-9958(84)80012-1]
• 13: Ford, L. R. and D. R. Fulkerson, Flows in Networks, Princeton University Press (1962).
• 14: 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]
• 15: Michel X. Goemans , David P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 16: Grötschel, M., L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1:169--197 (1981)
• 17: Györi, E., A min-max theorem on intervals, JCT B 37 (1984), pp. 1--9.
• 18: Hopcroft, J. E. and R. M. Karp, An n5/2 algorithm for maximum matching in bipartite graphs, SIAM J. Comp.2 (1973), pp. 225--231.
• 19: Tibor Jordán, On the optimal vertex-connectivity augmentation, Journal of Combinatorial Theory Series B, v.63 n.1, p.8-20, Jan. 1995 [doi>10.1006/jctb.1995.1002]
• 20: David R. Karger , Matthew S. Levine, Finding maximum flows in undirected graphs seems easier than bipartite matching, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.69-78, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276714]
• 21: Donald E. Knuth, Irredundant intervals, Journal of Experimental Algorithmics (JEA), 1, p.1-es, 1996 [doi>10.1145/235141.235146]