图论相关 独立集

LiLiLi_99

在一个连通图（所有边长皆为1）中，如何尽可能多地寻找一组 最小距离大于d 的点集合？

Max Independent Set是最小间距为2的点集（对于二分图已有匈牙利算法可以在多项式时间内解决），如果想寻找最小间距大于2（比如5）的点集有相关算法吗？

Nicolas2050

DOI：

10.1007/978-3-642-13731-0_7

Nicolas2050

max independent set is a paradigmatic problem in theoretical computer science and numerous studies tackle its resolution by exact algorithms with non-trivial worst-case com-plexity, both in the general case and in the case of bounded degree graphs. Here, we improve several of these results. We first get an algorithm in O * (1.0854 n) for graphs of average de-gree 3 using a case analysis based upon a detailed case analysis using several reduction rules. Then we propose a generic method showing how improvement of the worst-case complex-ity for max independent set in graphs of average degree d entails improvement of it in any graph of average degree greater than d and, based upon it, we tackle max indepen-dent set by improving its complexity in graphs of average degree 4, 5 and 6. Finally, we combine this method with measure and conquer techniques to get improved running times for general graphs. The best computation bounds obtained are O * (1.1571 n), O * (1.1918 n) and O * (1.2070 n), for graphs of maximum degree 4, 5 and 6 respectively, and O * (1.2125 n) for general graphs

Nicolas2050

许多学者提出了不同的MIS求解方法，这些方法可以归为如下三类：

（1）精确算法。MIS问题是NP难的，暴力求解并适当剪枝的方法虽然能求出精确解，但通常需要指数时间复杂度，效率不高。

（2）近似算法。近似算法求解MIS的近似解，并给出误差上界，时间复杂度较精确算法得到很大改进。

（3）启发式算法。这是一类线性时间或近似线性时间的算法，通过贪心的方法，逐步扩大顶点集合，使其仍满足独立集的性质。缺点是得到得独立集是近似解，且没有误差估计。

Nicolas2050

近年来，出现了很多基于学习（learning based）的方法求解NP难的问题。通常对于NP难的问题，如果在意运行时间，我们只能寄希望于启发式方法。而基于学习的方法通常能通过大量训练数据，发现人类设计者难以察觉的模式和规则帮助问题的求解。