Hostname: page-component-7c8c6479df-ph5wq Total loading time: 0 Render date: 2024-03-27T14:52:35.490Z Has data issue: false hasContentIssue false

Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time

Published online by Cambridge University Press:  03 January 2006

ALEXANDER D. SCOTT
Affiliation:
Department of Mathematics, University College London, London WC1E 6BT, UK (e-mail: scott@math.ucl.ac.uk)
GREGORY B. SORKIN
Affiliation:
Department of Mathematical Sciences, IBM T.J. Watson Research Center, Yorktown Heights NY 10598, USA (e-mail: sorkin@watson.ibm.com)

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 \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.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)