这个问题是 NP-完全 的 (Garey and Johnson 1983)。
最大独立集问题
另请参阅
无爪图, 独立集, 最大独立边集, 最大独立顶点集参考文献
Garey, M. R. 和 Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. 纽约: W. H. Freeman, 1983.Minty, G. J. "On Maximal Independent Sets of Vertices in Claw Free Graphs." J. Combin. Th. B 28, 284-304, 1980.Skiena, S. "Maximum Independent Set." §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. 马萨诸塞州雷丁: Addison-Wesley, pp. 218-219, 1990.Wolfram|Alpha 参考资料
最大独立集问题请引用为
Weisstein, Eric W. "最大独立集问题。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/MaximumIndependentSetProblem.html