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 have 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 l1-embeddability of a rational metric on an n-set (as opposed to one 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: D. Applegate, R. Bixby, V. Chvátal, and W. Cook. On the solution of traveling salesman problems. Documenta Mathematica, Extra Volume ICM 1998(3):645--656, 1998.
• 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: T. S. Arthanari. On the traveling salesman problem. Presented at the XI Symposium on Mathematical Programming held at Bonn, West Germany, 1982.
• 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: T. S. Arthanari and M. Usha. On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem. Operations Res. Letters, 29(3):129--139, 2001.
• 7: D. Avis and M. Deza. The cut cone, l¹ embeddability, complexity and multicommodity flows. Networks, 21:595--617, 1991.
• 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: R. D. Carr. Polynomial separation procedures and facet determination for inequalities of the traveling salesman polytope. PhD thesis, Carnegie Mellon University, 1995.
• 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: R. D. Carr and G. Lancia. Compact vs. exponential-size LP relaxations. Operations Res. Letters, 30:57--65, 2002.
• 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: M. Conforti, G. Rinaldi, and L. Wolsey. On the cut polyhedron. Technical Report 5, CORE, Université catholique de Louvain, 2000.
• 14: G. Dantzig, D. Fulkerson, and S. Johnson. Solution of a large-scale traveling salesman problem. J. of the Operations Res. Soc. of America, pages 393--410, 1954.
• 15: M. Deza and M. Laurent. Geometry of cuts and metrics. Springer-Verlag, 1997.
• 16: 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]
• 17: 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]
• 18: M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, Berlin, 1988.
• 19: K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21:39--60, 2001.
• 20: 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]
• 21: 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]
• 22: L. Lovász. Combinatorial Problems and Exercises. North-Holland, Amsterdam, 1979.
• 23: T. L. Magnanti and L. A. Wolsey. Optimal trees. In Network models, volume 7 of Handbooks in Operations Research, pages 503--615. Elsevier, 1995.
• 24: R. K. Martin. Using separation algorithms to generate mixed integer model reformulations. Operations Res. Letters, 10:119--128, 1991.
• 25: 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]
• 26: A. Schrijver. Combinatorial optimization: Polyhedra and Efficiency. Springer, 2003. Schrijver.
• 27: 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]
• 28: A. Tamir. Polynomial formulations of min-cut problems. Unpublished manuscript, 1994.
• 29: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 30: M. Yannakakis. Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci., 43(3):441--466, 1991.