网络是复杂系统中近邻关系的一种直观表示，它由节点和边组成，节点代表系统的组成单元，每条边连接两个节点，意味着某种近邻关系。虽说网络上的边只连接两个节点，但网络组合优化问题所包含的约束却常常是多体约束。最小支配集合问题就是这样一个问题。

　　最小支配集合是由网络中一部分节点构成的，它具有这样的性质：第一，这个集合必须是最小的；第二、如果某个节点不在该集合里面，那它至少有一个邻居在里面。换句话说，通过先访问最小支配集合，最多只需再跳一步就可访问到网络中任何一个节点。最小支配集合对于解决资源优化配置、网络搜索等问题很是重要。

　　每个节点带来一个多体约束：或者它自己，或者它的某个邻居，必须属于最小支配集合。如果某节点没有邻居，那它必须属于最小支配集合。如果某节点 i 只有一个邻居 j 而该邻居自己还有其它邻居，那么将 j 放进最小支配集合更为经济，因为这样的话，j 的所有邻居（包括 i）都不必属于最小支配集合了。

　　理论物理研究所研究员周海军的研究团队对最小支配集合问题进行过深入研究 [1]。他们注意到上述化简方法对于实际网络系统效果有限，简化之后网络仍然包含很多节点和边，不能得到精确的全局最优解。最近，周海军研究员参与的葡萄牙、美国、中国合作研究对于超网络的一般覆盖问题进行了理论探索 [2]。该论文发现如果将最小支配集合问题表述为超网络的覆盖问题，即将每个节点 i 的约束用一条超边来表示，该超边连接节点 i 和它的所有邻居，然后在超网络上优化问题进行化简，常常能导致问题被简化更多，有时甚至直接达到全局最优解。

　　图一：GLR （普通网络化简方法 [1]）；Hypergraph （超网络化简方法 [2]）；Core （化简后网络的大小）；横轴是不同的实际测试网络 　　 

　　这一工作表明用超网络表示来处理普通网络多体约束问题，将连接两个节点的边推广为连接多个节点的超边，有可能带来算法上的较大改进。更多理论细节，参见文献 [2]。 

　　[1]  J.-H. Zhao, Y. Habibulla, H.-J. Zhou, Statistical mechanics of the minimum dominating set problem, Journal of Statistical Physics 159, 1154 (2015).

　　[2]  B. C. Coutinho, A.-K. Wu, H.-J. Zhou, Y.-Y. Liu, Covering problems and core percolations on hypergraphs, Physical Review Letters 124, 248301 (2020).