Solving Sparse Semi-Random Instances of Max Cut and Max CSP

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, or Max 2-CSPs. In addition to Max Cut, 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(n, c/n), then the instance is solved in expected linear time if c 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” 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 n vertices and m edges, then nO(2(m-n)/2) is a deterministic upper bound on the solution time. Then, analyzing 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.

By: Alexander D Scott; Gregory B. Sorkin

Published in: RC23417 in 2004


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .