将一般独立集问题归约到3-可着色图后，如何推导原图最大独立集？

核心结论 #

设原图G的边数为m，α(G)表示G的最大独立集大小，α(G')表示构造得到的3-着色图G'的最大独立集大小，则二者满足：

α(G) = α(G') - m

推导过程 #

1. 从G的最大独立集构造G'的独立集 #

设S是G的一个最大独立集（|S|=α(G)），我们可以构造G'的独立集S'：

• 包含S中的所有原图顶点；
• 对每条边e=(u,v)对应的路径u−wₑ−xₑ−v：
  • 若u∈S（此时v∉S，因为S是独立集）：选择xₑ（xₑ与u不相邻，且v∉S，无冲突）；
  • 若v∈S：选择wₑ；
  • 若u∉S且v∉S：由于S是G的最大独立集，u和v必然与S中的某个顶点相邻（否则可将u/v加入S得到更大的独立集），因此u和v不能加入S'，此时选择wₑ或xₑ二者之一（二者互相相邻，只能选一个）。

每条边恰好贡献1个新增顶点，因此|S'|=α(G)+m，这说明α(G')≥α(G)+m。

2. 从G'的最大独立集推导G的独立集 #

设T是G'的一个最大独立集（|T|=α(G')），构造G的顶点集合S=T∩V(G)（即T中的原图顶点）：

• 若T中同时包含某条边e=(u,v)的两个端点u和v（G中u与v相邻），则T在路径u−wₑ−xₑ−v中只能选u和v（因为wₑ与u相邻，xₑ与v相邻），此时S不是独立集。我们可以调整T：去掉v，加入xₑ，得到的新集合仍是独立集且大小不变；重复此操作直到S是独立集。
• 调整后的T中，每条边对应的路径最多贡献1个新增顶点，因此|T|≤|S|+m。

由于T是最大独立集，|T|=α(G')，且|S|≤α(G)，因此α(G')≤α(G)+m。

3. 联立等式 #

结合上述两部分结论：α(G')≥α(G)+m且α(G')≤α(G)+m，因此α(G)=α(G')−m。

内容的提问来源于stack exchange，提问作者Mason Kane