Abstract
We show that a random instance of a weighted maximum constraint satisfaction problem (or max 2-csp), whose clauses are over pairs of binary variables, is solvable by a deterministic algorithm in polynomial expected time, in the “sparse” regime where the expected number of clauses is half the number of variables. In particular, a maximum cut in a random graph with edge density 1/n or less can be found in polynomial expected time.
Our method is to show, first, that if a max 2-csp has a connected underlying graph with n vertices and m edges, the solution time can be deterministically bounded by 2(m − n)/2. Then, analyzing the tails of the distribution of this quantity for a component of a random graph yields our result. An alternative deterministic bound on the solution time, as 2m/5, improves upon a series of recent results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bollobás, B., Borgs, C., Chayes, J.T., Kim, J.H., Wilson, D.B.: The scaling window of the 2-SAT transition. Random Structures Algorithms 18(3), 201–256 (2001)
Bollobás, B.: Random graphs. Cambridge Studies in Advanced Mathematics, vol. 73. Cambridge University Press, Cambridge (2001)
Coppersmith, D., Gamarnik, D., Hajiaghayi, M., Sorkin, G.B.: Random MAX SAT, random MAX CUT, and their phase transitions, 49 pages (submitted for publication)
Coppersmith, D., Gamarnik, D., Hajiaghayi, M., Sorkin, G.B.: Random MAX SAT, random MAX CUT, and their phase transitions. In: Proceedings of the 14th Annual ACM–SIAM Symposium on Discrete Algorithms, Baltimore, MD. ACM, New York (2003)
Coja-Oghlan, A., Moore, C., Sanwalani, V.: Max k-cut and approximating the chromatic number of random graphs (to appear)
Chvátal, V., Reed, B.: Mick gets some (the odds are on his side). In: 33th Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, pp. 620–627. IEEE Comput. Soc. Press, Los Alamitos (1992)
Wenceslas Fernandez de la Vega, On random 2-SAT (1992) (manuscript)
Gramm, J., Hirsch, E.A., Niedermeier, R., Rossmanith, P.: New worst-case upper bounds for MAX-2-SAT with an application to MAXCUT. Discrete Applied Mathematics (in press)
Goerdt, A.: A threshold for unsatisfiability. J. Comput. System Sci. 53(3), 469–486 (1996)
Kulikov, A.S., Fedin, S.S.: Solution of the maximum cut problem in time 2|E|/4, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov(POMI) 293, no. Teor. Slozhn. Vychisl. 7, 129–138, 183 (2002)
Krivelevich, M., Vu, V.H.: Approximating the independence number and the chromatic number in expected polynomial time. J. Comb. Optim. 6(2), 143–155 (2002)
Taraz, A., Coja-Oghlan, A.: Colouring random graphs in expected polynomial time. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 487–498. Springer, Heidelberg (2003)
Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074–2097 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Scott, A.D., Sorkin, G.B. (2003). Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds) Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques. RANDOM APPROX 2003 2003. Lecture Notes in Computer Science, vol 2764. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45198-3_32
Download citation
DOI: https://doi.org/10.1007/978-3-540-45198-3_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40770-6
Online ISBN: 978-3-540-45198-3
eBook Packages: Springer Book Archive