Random MAX SAT, random MAX CUT, and their phase transitions

ABSTRACT

With random inputs, certain decision problems undergo a "phase transition". We prove similar behavior in an optimization context.Specifically, random 2-SAT formulas with clause/variable density less than 1 are almost always satisfiable, those with density greater than 1 are almost always unsatisfiable, and the "scaling window" is in the density range 1 ± Θ (n^-1/3). We prove a similar phase structure for MAX 2-SAT: for density c < 1, the expected number of clauses satisfiable is [cn] -- Θ(1/n); within the scaling window it is [cn] -- Θ(1); and for c > 1, it is ¾[cn] + Θ(n). (Our results include further detail.)For random graphs, a maximization version of the giant-component question behaves quite differently from 2-SAT, but MAX CUT behaves similarly.For optimization problems, there is also a natural analog of the "satisfiability threshold conjecture". Although here too it remains just a conjecture, it is possible that optimization problems may prove easier to analyze than their decision analogs, and may help to elucidate them.

REFERENCES

• 1: D. Achioptas , G. B. Sorkin, Optimal myopic algorithms for random 3-SAT, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.590, November 12-14, 2000
• 2: Béla Bollobás , Christian Borgs , Jennifer T. Chayes , Jeong Han Kim , David B. Wilson, The scaling window of the 2-SAT transition, Random Structures & Algorithms, v.18 n.3, p.201-256, May 2001 [doi>10.1002/rsa.1006]
• 3: Alberto Bertoni , Paola Campadelli , Roberto Posenato, An Upper Bound for the Maximum Cut Mean Value, Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, p.78-84, June 18-20, 1997
• 4: Tom Bohman , Alan Frieze, Avoiding a giant component, Random Structures & Algorithms, v.19 n.1, p.75-85, August 2001 [doi>10.1002/rsa.1019]
• 5: Andrei Z. Broder , Alan M. Frieze , Eli Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.322-330, January 25-27, 1993, Austin, Texas, United States
• 6: {BFW02} Tom Bohman, Alan M. Frieze, and Nicholas C. Wormald, Avoiding a giant component II, Unpublished manuscript, February 2002.
• 7: {Bo198} Béla Bollobás, Modern graph theory, Springer, New York, 1998.
• 8: {CR92a} Vasěk Chvátal and Bruce Reed, Mick gets some (the odds are on his side), 33th Annual Symposium on Foundations of Computer Science (Pittsburgh, PA, 1992), IEEE Comput. Soc. Press, Los Alamitos, CA, 1992, pp. 620--627.
• 9: {CR92b} Vasěk Chvátal, Mick gets some (the odds are on his side), 33th Annual Symposium on Foundations of Computer Science (Pittsburgh, PA, 1992), IEEE Comput. Soc. Press, Los Alamitos, CA, 1992, pp. 620--627.
• 10: {FdlV92} Wenceslas Fernandez de la Vega, On random 2-SAT, Manuscript, 1992.
• 11: {Fri991 Ehud Friedgut, Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-SAT problem, J. Amer. Math. Soc. 12 (1999), 1017--1054.
• 12: Andreas Goerdt, A threshold for unsatisfiability, Journal of Computer and System Sciences, v.53 n.3, p.469-486, Dec. 1996 [doi>10.1006/jcss.1996.0081]
• 13: 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]
• 14: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 15: {JS02} Svante Janson and Gregory B. Sorkin, Personal communication, 2002.
• 16: Svante Janson , Yannis C. Stamatiou , Malvina Vamvakari, Bounding the unsatisfiability threshold of random 3-SAT, Random Structures & Algorithms, v.17 n.2, p.103-116, Sept. 2000 [doi>10.1002/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P]
• 17: Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.406, October 19-22, 1997
• 18: Michael Lewin , Dror Livnat , Uri Zwick, Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.67-82, May 27-29, 2002
• 19: {Spe94} Joel H. Spencer, Ten lectures on the probabilistic method, second ed., SIAM, 1994.
• 20: Luca Trevisan , Gregory B. Sorkin , Madhu Sudan , David P. Williamson, Gadgets, Approximation, and Linear Programming, SIAM Journal on Computing, v.29 n.6, p.2074-2097, April 2000 [doi>10.1137/S0097539797328847]
• 21: {Wor95} Nicholas C. Wormald, Differential equations for random processes and random graphs, Ann. Appl. Probab. 5 (1995), no. 4, 1217--1235.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Algorithms, Theory