最大独立集的精确算法
本文研究了应用广泛的 NP-hard 问题之一，最大独立集问题（ M IS），提出了局部搜索框架 ARIR 及其三种算法，采用三种不同的减少策略，在五组基准测试中显示出明显的优越性。
Aug, 2022
本文提出了一种基于动态规划的图神经网络（GNN）框架来解决最大独立集（MIS）问题，通过递归算法构建子图并预测具有较大 MIS 的子图，进而在下一个递归调用中使用。我们通过对不同图形之间的 MIS 大小进行注释比较来训练算法，注释比较的输出结果用于自我训练过程，以提高注释比较的准确性。我们提供了在多个合成和真实数据集中证明我们算法优越性的数值证据。
Oct, 2023
本文通过研究贪婪顺序算法中迭代间的依赖结构，证明了随机排序后的贪婪最大独立集算法以及贪婪最大匹配算法的依赖深度为对数级别，提出了基于该结论设计的简单线性工作并行算法，该算法能在更高的并行度与更小的工作开销之间平衡，并且保证结果与顺序贪婪算法相同。
Feb, 2012
本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。
Jul, 2019
该论文引入了一种物理启发的无监督图神经网络以解决稀疏图上的组合优化问题，作者展示了在最大割和最大独立集问题上这些 GNNs 的性能可以与或优于现有求解器，并且具有处理百万变量问题的能力。然而，该评论提出了一个简单贪心算法可以找到比 GNN 更好的质量的解决方案。此外，该评论者还建议通过基于真正困难的问题的标准基准测试未来的神经网络优化器。
Jun, 2022
本研究证明：在随机图中，最大独立集问题的组合结构会在独立集大小 k 超过 k nln (d)/d 这个点时发生相变，形成一个错综复杂的景象，局部搜索算法难以摆脱。这一现象通过 Metropolis 过程，即一个用于采样独立集的马尔可夫链实现了指数下界。
Jul, 2010
在回复评论者的回复中，我们指出其关注的最大独立集（MIS）在稀疏图中和贪心算法优秀表现无关，我们还强调了原始框架中广泛的算法开发，并通过提供额外的数值结果证明了我们原来的结果的可观改进，进而驳斥了评论中的性能声明。我们同时通过实验证明了我们提出的随机 d - 正则图不提供用于基准测试的通用实例集，贪心算法不提供通用算法基线。最后，我们指出图神经网络的内在（并行）解剖与贪心算法的（顺序）本质非常不同，并强调图神经网络已经展示出了比现有启发式方法（如并行退火）更高的可扩展性潜力。这份工作的概念创新值得探讨并有潜力进一步拓展。
Feb, 2023