最小支配集是給定圖中最小尺寸的支配集。最小支配集的大小被稱為圖的支配數。
最小支配集總是極小支配集，但反之不一定成立。
找到一般圖的最小支配集是 NP 完全問題，這可以透過從頂點覆蓋問題的歸約來證明 (Garey and Johnson 1983, Mertens 2024)。這意味著不存在多項式時間演算法來計算最小支配集。已知最快的演算法找到具有頂點數 
的通用圖的最小支配集的時間複雜度為 
(van Rooij and Bodlaender 2011, Mertens 2024)。
最小支配集
另請參閱
支配數, 支配多項式, 支配集, 極小支配集使用 探索
參考文獻
Garey, M. R. 和 Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.Mertens, S. "Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph." 2024 年 8 月 15 日. https://arxiv.org/abs/2408.08053.van Rooij, J. M. M. 和 Bodlaender, H. L. "Exact Algorithms for Dominating Set." Discr. Appl. Math. 159, 2147-2164, 2011.請引用為
Weisstein, Eric W. "最小支配集。" 來自 Web 資源。 https://mathworld.tw/MinimumDominatingSet.html