Compacting cuts: A new linear formulation for minimum cut

ABSTRACT

For a graph (V,E), existing compact linear formulations for the minimum cut problem require Θ(|V||E|) variables and constraints and can be interpreted as a composition of |V| − 1 polyhedra for minimum s-t cuts in much the same way as early approaches to finding globally minimum cuts relied on |V| − 1 calls to a minimum s-t cut algorithm. We present the first formulation to beat this bound, one that uses O(|V|²) variables and O(|V|³) constraints. An immediate consequence of our result is a compact linear relaxation with O(|V|²) constraints and O(|V|³) variables for enforcing global connectivity constraints. This relaxation is as strong as standard cut-based relaxations and has applications in solving traveling salesman problems by integer programming as well as finding approximate solutions for survivable network design problems using Jain's iterative rounding method. Another application is a polynomial-time verifiable certificate of size n for for the NP-complete problem of l₁-embeddability of a rational metric on an n-set (as opposed to a certificate of size n² known previously).

REFERENCES

• 1: Mikhail Alekhnovich , Sanjeev Arora , Iannis Tourlakis, Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060634]
• 2: Applegate, D., Bixby, R., Chvátal, V., and Cook, W. 1998. On the solution of traveling salesman problems. Documenta Mathematica Extra Volume ICM 1998, 3, 645--656.
• 3: Sanjeev Arora , Béla Bollobás , László Lovász, Proving Integrality Gaps without Knowing the Linear Program, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.313-322, November 16-19, 2002
• 4: Arthanari, T. S. 1982. On the traveling salesman problem. XI Symposium on Mathematical Programming.
• 5: T.S. Arthanari , M. Usha, An alternate formulation of the symmetric traveling salesman problem and its properties, Discrete Applied Mathematics, v.98 n.3, p.173-190, Jan.15.2000 [doi>10.1016/S0166-218X(99)00154-7]
• 6: Arthanari, T. S., and Usha, M. 2001. On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem. Oper. Res. Lett. 29, 3, 129--139.
• 7: Avis, D., and Deza, M. 1991. The cut cone, l¹ embeddability, complexity and multi-commodity flows. Netw. 21, 595--617.
• 8: Cynthia Barnhart , Ellis L. Johnson , George L. Nemhauser , Martin W. P. Savelsbergh , Pamela H. Vance, Branch-And-Price: Column Generation for Solving Huge Integer Programs, Operations Research, v.46 n.3, p.316-329, March 1998 [doi>10.1287/opre.46.3.316]
• 9: Carr, R. D. 1995. Polynomial separation procedures and facet determination for inequalities of the traveling salesman polytope. Ph.D. thesis, Carnegie Mellon University.
• 10: Robert Carr, Separating over Classes of TSP Inequalities Defined by 0 Node-Lifting in Polynominal Time, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.460-474, June 03-05, 1996
• 11: Carr, R. D., and Lancia, G. 2002. Compact vs. exponential-size LP relaxations. Oper. Res. Lett. 30, 57--65.
• 12: Robert Carr , Santosh Vempala, Randomized metarounding, Random Structures & Algorithms, v.20 n.3, p.343-352, May 2002 [doi>10.1002/rsa.10033]
• 13: Claus, A. 1984. A new formulation for the travelling salesman problem. SIAM J. Algor. Disc. Meth. 5, 21--25.
• 14: 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]
• 15: Conforti, M., Rinaldi, G., and Wolsey, L. 2000. On the cut polyhedron. Tech. rep. 5, CORE, Université Catholique de Louvain.
• 16: Dantzig, G., Fulkerson, D., and Johnson, S. 1954. Solution of a large-scale traveling salesman problem. Oper. Res. 2, 393--410.
• 17: Deza, M., and Laurent, M. 1997. Geometry of Cuts and Metrics. Springer-Verlag.
• 18: Yefim Dinitz , Alek Vainshtein, The connectivity carcass of a vertex subset in a graph and its incremental maintenance, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.716-725, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195442]
• 19: András Frank, On a theorem of Mader, Discrete Mathematics, v.101 n.1-3, p.49-57, May 29, 1992 [doi>10.1016/0012-365X(92)90589-8]
• 20: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 21: Grötschel, M., Lovász, L., and Schrijver, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer, Berlin.
• 22: Jain, K. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 39--60.
• 23: David R. Karger, Minimum cuts in near-linear time, Journal of the ACM (JACM), v.47 n.1, p.46-76, Jan. 2000 [doi>10.1145/331605.331608]
• 24: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 25: Lovász, L. 1976. Unsolved problems. In Proceedings of the 5th British Combinatorial Conference. Utilitas Math., 683--685. Congressus Numerantium, No. XV.
• 26: Lovász, L. 1979. Combinatorial Problems and Exercises. North-Holland, Amsterdam.
• 27: Mader, W. 1978. A reduction method for edge-connectivity in graphs. Ann. Discrete Math. 3, 145--164.
• 28: Magnanti, T. L., and Wolsey, L. A. 1995. Optimal trees. In Network Models, M. O. Ball et al., Eds. Handbooks in Operations Research and Management Science, vol. 7. Elsevier, 503--615.
• 29: Martin, R. K. 1991. Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10, 119--128.
• 30: Hiroshi Nagamochi , Toshihide Ibaraki, Computing edge-connectivity in multigraphs and capacitated graphs, SIAM Journal on Discrete Mathematics, v.5 n.1, p.54-66, Feb. 1992 [doi>10.1137/0405004]
• 31: Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer. Schrijver.
• 32: Mechthild Stoer , Frank Wagner, A simple min-cut algorithm, Journal of the ACM (JACM), v.44 n.4, p.585-591, July 1997 [doi>10.1145/263867.263872]
• 33: A. Tamir, On the core of network synthesis games, Mathematical Programming: Series A and B, v.50 n.1, p.123-135, February 1991 [doi>10.1007/BF01594930]
• 34: Tamir, A. 1994. Polynomial formulations of min-cut problems. Unpublished manuscript. http://www.tau.ac.il/~atamir/min_cut_94.pdf
• 35: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 36: Wong, R. T. 1980. Integer programming formulations of the traveling salesman problem. In Proceedings of the IEEE Conference on Circuits and Computers, 149--152.
• 37: Wong, R. T. 1984. A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28, 271--287.
• 38: Yannakakis, M. 1991. Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43, 3, 441--466.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
      F.1.3 Complexity Measures and Classes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory

Keywords:
Linear programming formulation complexity, minimum cut problem