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 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 2~(m/5), improves upon a series of recent results.
展开▼
