《Discrete Applied Mathematics》：The Maximum Independent Set problem on circulant graphs Cn(a,b)
编辑推荐：
这篇综述深入探讨了4-正则连通循环图Cn(a,b)上的最大独立集（MIS）问题。作者从代数与组合视角出发，提出了一种基于图阵列表示的新方法，成功证明了该图的最大独立集基数可用一个与最小奇环横截集基数相关的简洁公式表示，并由此得出了该问题可在O(n)时间内求解的突破性结论。这一进展不仅解决了MIS问题本身，还连带证明了顶点覆盖数、奇环横截面（OCT）及分数色数等图不变量在同类图上同样具有线性时间复杂度算法，为相关计算图论领域提供了有力工具。
研究亮点
- •
我们为任意4-正则连通循环图Cn(a,b)上的最大独立集（MIS）问题提供了一个优雅的解析解。
- •
我们证明MIS的基数可以通过一个与最小奇环横截集基数相关的公式精确计算。
- •
基于此，我们开发了一种能在O(n)时间内解决此类图上MIS问题的高效算法。
- •
作为直接推论，顶点覆盖数、奇环横截面（OCT）以及分数色数在同类图上均可在线性时间内求解。
1. 引言
循环图是一类高度对称的数学结构，是凯莱图的特例，也是具有更高连通性的环状结构的自然推广。它们被广泛应用于离散细胞神经网络、小世界网络、化学反应、超级计算及多处理器系统等领域建模。
考虑t+1个非负整数n, a1, a2, …, at。循环图Cn(a1, a2, …, at)的顶点集V={v0, v1, …, vn-1}，边集E包含所有形如(vi, v(i+ah) mod n)的边。Cn(a1, a2, …, at)是2t-正则图。
本文聚焦于（简单无向）4-正则连通循环图Cn(a,b)。该图是连通的当且仅当gcd(n,a,b)=1，是二分图当且仅当n为偶数且a和b均为奇数。
我们研究任意Cn(a,b)=(V,E)上的最大独立集（MIS）问题。图G的独立集是其中任意两点均不相邻的顶点子集。MIS问题的目标是找到G中最大的独立集，其基数称为图的独立数，记为α(G)。若Cn(a,b)是二分图，则α(Cn(a,b))=n/2；若其不连通，则α(Cn(a,b))等于其连通分支数的p倍乘以各分支的独立数。
据我们所知，仅有少数文献在特定条件下研究了具有两个“跳数”的循环图（即t=2时）上的MIS问题，且大多仅评估了独立数α(G)，而我们的工作还能确定构成最大独立集的顶点。
2. 准备工作
（此处详细定义了循环图、最大独立集、分数色数、奇环横截面等相关概念及符号，为后续理论推导奠定了基础。）
3. 主要结果
本章节是我们的核心贡献所在。我们引入了一种基于循环图阵列表示的全新代数与组合方法。通过精心构建，我们证明了以下关键定理：
定理 3.1. 对于任意4-正则连通循环图Cn(a,b)，其最大独立集的基数α(Cn(a,b))可由公式 (n - |W|)/2 给出，其中|W|是覆盖图中所有奇环所需的最小顶点子集的基数。
这个定理揭示了MIS问题与奇环横截面（OCT）问题之间深刻而直接的联系。基于此，我们设计了一个高效的构造性算法。
定理 3.2. 在任意Cn(a,b)上求解最大独立集（MIS）问题可以在O(n)时间内完成。
该算法的线性时间复杂度是一个显著的突破。更重要的是，由于最大独立集、最小顶点覆盖、奇环横截面以及分数色数等图参数之间的内在联系，我们得到了一个强大的推论：
推论 3.3. 在任意4-正则连通循环图Cn(a,b)上，最小顶点覆盖数、最小奇环横截集（OCT）基数以及分数色数χf(Cn(a,b))均可通过线性时间算法计算。
4. 证明与技术细节
（本部分通过严格的数学推导证明了定理3.1。我们首先将图的顶点排列成一个矩形阵列，利用循环图的对称性，将全局的独立集问题转化为对阵列“行”的局部模式分析。接着，我们刻画了阵列中代表奇环的结构，并证明了任何最大独立集都必须避开这些奇环上的特定顶点模式。最终，通过分析最小奇环横截集W的性质，我们得出了MIS基数的精确表达式。定理3.2的证明则基于对W的线性时间构造。）
5. 结论
本文彻底解决了4-正则连通循环图Cn(a,b)上的最大独立集问题。我们不仅给出了独立数的解析表达式，更重要的是，我们提出了一种新颖的阵列表示法，并由此开发出首个能在O(n)线性时间内解决此问题的算法。
我们的方法具有一般性，所建立的框架清晰地展示了MIS、顶点覆盖、OCT和分数色数等经典图论问题在此类高度结构化图上的可计算性。这一成果不仅推进了对循环图组合性质的理论理解，也为相关实际应用（如网络设计、调度优化等）提供了高效的算法工具。
未来的研究方向可能包括将此类代数组合方法推广到更一般的循环图（如度数更高或跳数更多的循环图），或探索其他图类上类似问题的可高效求解条件。
