An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems

ABSTRACT

Efficient algorithms are given for the bidirected network flow problem and the degree-constrained subgraph problem. Four versions of each are solved, depending on whether edge capacities/multiplicities are one or arbitrary, and whether maximum value/maximum cardinality or minimum cost/maximum weight is the objective. A version of the shortest path problem is also efficiently solved. The algorithms use a reduction technique that solves one problem instance by reducing to a number of problems.

REFERENCES

• 1: R.P. Anstee, "An algorithmic proof of Tutte's f-factor theorem", Res. Rept. CORR 81-28, Dept. of Combinatorics and Optimization, Univ. of Waterloo, Waterloo, Ontario, 1981.
• 2: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 3: R. Bernstein, "Shortest paths in undirected graphs", M.S. Thesis, Stevens Inst. Technology, 1982.
• 4: G.B. Dantzig, Linear Programming and Extensions, Princeton Univ. Press, Princeton, NJ, 1963.
• 5: Edmonds, J., "Maximum matching and a polyhedron with 0,1-vertices," J. Res. Nat. Bur. Standards 69B (1965), 125-130.
• 6: J. Edmonds, "An introduction to matching," Notes of Engineering Summer Conference, Univ. of Michigan, Ann Arbor, 1967.
• 7: J. Edmonds and E.L. Johnson, "Matching: A well-solved class of integer linear programs," Proc. Calgray Int. Conf. on Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970, pp. 89-92.
• 8: J. Edmonds and E.L. Johnson, "Matching, Euler tours and the Chinese postman," Math. Programming 5, 1973, pp. 88-124.
• 9: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 10: S. Even and R.E. Tarjan, "Network flow and testing graph connectivity", SIAM J, Comput. 4, 4, 1975, pp. 507-518.
• 11: H. Gabow, "An efficient reduction technique for degree-constrained subgraph and bidirectied network flow problems," Tech. Rept. CU-CS-243-83, University of Colorado, Boulder, Colorado, 1983.
• 12: H. Gabow, "An efficient implementation of Edmonds' algorithm for maximum weight matching on graphs," Tech. Rept. CU-CS-075-75, University of Colorado, Boulder, Colorado, 1975.
• 13: A.J. Goldman, "Optimal matchings and degree-constrained subgraphs," J. Res. National Bureau of Standards 68B, 1, 1964, pp. 27-29.
• 14: Z. Galil, S. Micali, H. Gabow, "Priority queues with variable priority and an O(E V log V) algorithm for finding a maximal weighted matching in general graphs," Proc. 23rd Annual Symp. on Foundation of Comp. Sci., 1982, pp. 225-261.
• 15: H.N. Gabow and M. Stallman, "Scheduling multitask jobs with deadlines on one processor," abstract.
• 16: Hopcroft, J. and Karp, R, "An n5/2 algorithm for maximum matchings in bipartite graphs," SIAM. J. Comp. 2, 4, 1973, pp. 225-231.
• 17: E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
• 18: S. Micali and V.V. Vazirani, "An 0((@@@@)V.E) algorithm for finding maximum matching in general graphs," Proc. 21st Annual Symp. on Found. of Comp. Sci., 1980, pp. 17-27.
• 19: Y. Shiloach, "Another look at the degree constrained subgraph problem," Inf. Proc. Letters 12, 2, 1981, pp. 89-92.
• 20: Daniel Dominic Kaplan Sleator, An o(nm log n) algorithm for maximum network flow, 1981
• 21: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.114-122, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802464]
• 22: R.E. Tarjan, "Shortest paths," Ch. 17 in unpublished manuscript. 1982.
• 23: R.J. Urquhart, "Degree-constrained subgraphs of linear graphs," Ph.D. Diss., University of Michigan, 1967.
• 24: L.J. White, "A parametric study of matchings and covering in weighted graphs," Ph.D. Diss., Systems Eng. Lab., Dept. of Electrical Eng., University of Michigan. Ann Arbor, 1967.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Theory