Heuristics for Semirandom Graph Problems
Heuristics for Semirandom Graph Problems
复制标题
半随机图问题的启发式方法
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
J. Kilian
中科院分区：
文献类型：
--
作者：
U. Feige;J. Kilian
我们考虑在图形中找到大型独立集，颜色和两种模型，通过融合随机和对抗性的决策来生成问题与s连接S的边缘是用概率P选择的，然后允许对手任意添加新的边缘，前提是S是独立的集合p是，对手在semirandom图上具有越大的控制。我们表明，当p <（1 ??）lnn /？n，除非np？引入了K色的Semrandom图blum和spencer对于常数k，我们的结果是恒定的因素，在图形分式的半越野赛中。 ）是用概率q独立选择的，每个边缘（u，v）？s×s可以独立选择概率PQ。扩展工作Boppana，我们给出了一种启发式，当p？q？cplogn/n时，对于c一个足够大的常数时，恢复了这一二分分的可能性。
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 ?n vertices is randomly chosen. Each edge connecting S with S 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 ?n whenever p> (1+?)lnn/?n, for any constant ?>0. We show that when p<(1??)lnn /?n, an independent set of size |S| cannot be recovered, unless NP?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) of the vertices is chosen. Each edge (u, v)?S×S is independently chosen with probability q and each edge (u, v)?S×S is independently chosen with probability pq. The adversary may then arbitrarily remove edges in S×S and add edges not in S×S. Extending the work of Boppana, we give a heuristic that recovers this bisection with high probability when p?q?cplogn/n, for c a sufficiently large constant.