Heuristics for semirandom graph problems

We consider semirandom graph models for finding large independent sets, colorings, and bisections in graphs. These models generate problem instances by blending random and adversarial decisions. To generate semirandom independent set problems, an independent set S of an vertices is randomly chosen. Each edge connecting S with (S) over bar is chosen with probability p, and an adversary is then allowed to add new edges arbitrarily, provided that S remains an independent set. The smaller p is, the greater the control the adversary has over the semirandom graph. We give a heuristic that with high probability recovers an independent set of size alphan whenever p > (1 + epsilon) In n/alphan, for any constant epsilon > 0. We show that when p < (I - epsilon) In n/an, an independent set of size \S\ cannot be recovered, unless NP subset of or equal to BPP. We use our result for maximum independent sets to obtain greatly improved heuristics for the model of k-colorable semirandom graphs introduced by Blum and Spencer. For constant k, our results are optimal up to constant factors in the edge probabilities. In the semirandom model for graph bisection, a random bisection (S, (S) over bar) of the vertices is chosen. Each edge (u, v) is an element of S x (S) over bar is independently chosen with probability q and each edge (u, v) is not an element of S x (S) over bar is independently chosen with probability p > q. The adversary may then arbitrarily remove edges in S x (S) over bar and add edges not in S x (S) over bar. Extending the work of Boppana, we give a heuristic that recovers this bisection with high probability when p - q greater than or equal to c rootp log n/n, for c a sufficiently large constant. (C) 2001 Elsevier Science (USA).