Resource title

Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time

Resource image

image for OpenScout resource :: Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time

Resource description

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 \in \mathcal{G}(n,c/n)$, then the instance is solved in linear expected time if $c \leq 1$. Moreover, for arbitrary values (or functions) $c>1$ an instance is solved in expected time $n \exp(O(1+(c-1)^3 n))$; in the ‘scaling window’ $c=1+\lambda n^{-1/3}$ with $\lambda$ fixed, this expected time remains linear. Our method is to show, first, that if a Max 2-CSP has a connected underlying graph with $n$ vertices and $m$ 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.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/35466/

Resource license