Linear phase transition in random linear constraint satisfaction problems

ABSTRACT

Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints C on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from C also uniformly at random. This procedure is repeated m times independently. We are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition, when n ← ∞ and m = cn for a constant c. Namely, there exists a critical value c* such that, when c < c*, the problem is feasible or is asymptotically almost feasible, as n ← ∞, but, when c > c*, the "distance" to feasibility is at least a positive constant independent of n. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [Ald92], [Ald01], Aldous and Steele [AS03], Steele [Ste02] and martingale techniques. By exploiting a linear programming duality, our theorem implies some results for maximum weight matchings in sparse random graphs G(n, ⌊cn⌋) on n nodes with cn edges, where edges are equipped with randomly generated weights.

REFERENCES

• 1: {Ald92} D. Aldous, Asymptotics in the random assignment problem, Probab. Th. Rel. Fields (1992), no. 93, 507--534.
• 2: David J. Aldous, The ζ (2) limit in the random assignment problem, Random Structures & Algorithms, v.18 n.4, p.381-418, July 2001 [doi>10.1002/rsa.1015]
• 3: Dimitris Achlioptas , Cristopher Moore, The Asymptotic Order of the Random k -SAT Threshold, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.779-788, November 16-19, 2002
• 4: {ANP} D. Achlioptas, A. Naor, and Y. Peres, On the maximum satisfiability of random formulas, Preprint.
• 5: {AP} D. Achlioptas and Y. Peres, The threshold for random k-SAT is 2k(ln 2 + o(1)), Submitted.
• 6: Jonathan Aronson , Alan Frieze , Boris G. Pittel, Maximum matchings in sparse random graphs: Karp-Sipser revisited, Random Structures & Algorithms, v.12 n.2, p.111-177, March 1998 [doi>10.1002/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#]
• 7: {AS03} D. Aldous and J. M. Steele, The objective method: Probabilistic combinatorial optimization and local weak convergence, Discrete Combinatorial Probability, H. Kesten Ed., Springer-Verlag, 2003.
• 8: Don Coppersmith , David Gamarnik , Mohammad Hajiaghayi , Gregory B. Sorkin, Random MAX SAT, random MAX CUT, and their phase transitions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: {CR92} V. Chvatal and B. Reed, Mick gets some (the odds are on his side), Proc. 33d Symposium on Foundations of Computer Science (1992).
• 10: Olivier Dubois , Yacine Boufkhad , Jacques Mandler, Typical random 3-SAT formulae and the satisfiability threshold, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.126-127, January 09-11, 2000, San Francisco, California, United States
• 11: {dlV92} W. Fernandez de la Vega, On random 2-SAT, Unpublished manuscript (1992).
• 12: {Dur96} R. Durrett, Probability: theory and examples, Duxbury Press, second edition, 1996.
• 13: {Fri99} E. Friedghut, Sharp thresholds of graph proprties, and the k-SAT problem, J. Amer. Math. Soc. 4 (1999), 1017--1054.
• 14: {FW02} A. Frieze and N. Wormald, Random k-SAT: A tight threshold for moderately growing k, Proceedings of the Fifth International Symposium on Theory and Applications of Satisfiability Testing, 2002, pp. 1--6.
• 15: {Gam02} D. Gamarnik, Linear phase transition in random linear constraint satisfaction problems, Submitted, 2002.
• 16: {GNS03} D. Gamarnik, T. Nowicki, and Grzegorz Swirscsz, Maximum weight independent sets and matchings in sparse random graphs. exact results using the local weak convergence method, Preprint (2003).
• 17: Andreas Goerdt, A Treshold for Unsatisfiability, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.264-274, August 24-28, 1992
• 18: 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]
• 19: {JLR00} S. Janson, T. Luczak, and A. Rucinski, Random graphs, John Wiley and Sons, Inc., 2000.
• 20: {KKL02} A. C. Kaporis, L. M. Kirousis, and E. Lalas, The probabilistic analysis of a greedy satisfiability algorithm, 5-th International Symposium on the Theory and Applications of Satisfiability Testing, 2002, pp. 362--376.
• 21: {KS81} R. Karp and M. Sipser, Maximum matchings in sparse random graphs, 22nd Annual Symposium on Foundations of Computer Science, 1981, pp. 364--375.
• 22: {MP87} M. Mezard and G. Parisi, On the solution of the random link matching problem, J. Physique 48 (1987), 1451--1459.
• 23: {PS98} C. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity, Dover, 1998.
• 24: {Ste02} J. M. Steele, Minimal spanning trees for graphs with random edge lenghts, Mathematics and Computer Science II. Algorithms, Trees, Combinatorics and Probabilities. (2002), 223--246.