About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Combinatorics Probability and Computing
Paper
Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time
Abstract
We show that a maximum cut of a random graph below the giant-component threshold can be found in linear space and linear expected time by a simple algorithm. In fact, the algorithm solves a more general class of problems, namely binary 2-variable constraint satisfaction problems. In addition to Max Cut, such Max 2-CSPs encompass Max Dicut, Max 2-Lin, Max 2-Sat, Max-Ones-2-Sat, maximum independent set, and minimum vertex cover. We show that if a Max 2-CSP instance has an 'underlying' graph which is a random graph G ∈ script G sign(n,c/n), then the instance is solved in linear expected time if . Moreover, for arbitrary values (or functions) c > 1 an instance is solved in expected time ; in the 'scaling window' c = 1 + λ n-1/3 with λ fixed, this expected time remains linear. Our method is to show, first, that if a Max 2-CSP has a connected underlying graph with vertices and edges, then O(n 2(m-n)/2} is a deterministic upper bound on the solution time. Then, analysing the tails of the distribution of this quantity for a component of a random graph yields our result. Towards this end we derive some useful properties of binomial distributions and simple random walks. © 2006 Cambridge University Press.