完美图的电力控制集问题及其推广问题的算法研究

Domination theory in graphs is now one of the fastest-growing areas within graph theory. The study of this problem is extensive and in-depth with the introduction of different kinds of domination problems. At present, more and more researchers begin to pay attention to power domination problem due to its special conditions and applications. View from the present research progress, there are many unsolved issues for this problem in perfect graphs compared to the results of classic domination problem. Thus this project is to investigate power domination problem in perfect graphs. The major research topics include: (1) Using polynomial-time reduction to determine the sub-classes of perfect graphs for which power domination problem is NP-complete. (2) Utilizing some methods, such as labeling method, dynamic programming, linear programming, etc, to design some polynomial-time algorithms in some sub-classes of perfect graphs; (3) Introduction of a new generalization of power domination problem, named f-power domination problem, and some polynomial-time algorithms will be given for this new problem in some special graphs, such as trees, interval graphs, etc. The purpose of this project is to design some new algorithms and obtain some new in-depth results, which can make domination theory in graphs more perfect.

图的控制集理论是目前图论研究中发展最快的领域之一，并且随着各种形式控制集问题的引入，其研究更为广泛而深入。电力控制集问题以其独特的控制条件和较强的应用背景，目前已经引起很多学者的关注。从现有的研究状况来看，该问题在完美图上的研究成果较经典的控制集问题而言有较大的"缺口"。故本项目拟对电力控制集问题在完美图上做一些研究工作，主要的研究内容为：一、用多项式时间归约确定电力控制集问题在完美图的哪些子图类上是NP-完全的；二、用标号方法、动态规划、线性规划等方法设计电力控制集问题在完美图的子图类上的多项式时间算法；三、引入电力控制集问题的推广形式f-电力控制集问题，并给出其在一些图类(如树、区间图等)上的多项式时间算法。通过本项目的研究，能得到一些新的算法和较深刻的新结果，进一步完善图的控制集理论。

图的控制集理论是目前图论研究的热点之一，其作为运筹学中选址问题的数学模型具有很强的应用背景。本项目针对几类控制集问题进行了算法方面的研究，主要成果包括：(1) 设计了一个块图(Block graph)上的k-电力控制集问题的多项式时间算法并给出了正确性证明，该算法推广了台湾大学张镇华教授等人提出的k-电力控制集问题在树上的算法；（2）证明了全限制控制集(Total restrained domination)问题在平面图和分裂图上是NP-完全的，该结果将先前提出的全限制控制集在弦图上的NP-完全的结果缩小到分裂图中；（3）在树上提出了一个多项式时间算法，该算法能判断一个给定的节点是否包含在所有的最小k-配对控制集中，该结果推广了Chen和Henning等人分别与2007年和2005年给出的关于配对控制集的结果；（4）在树中构造了两个树的集合，两个集合中的树分别具有相同的电力控制数和全控制数以及相同的电力控制数和独立控制数。通过本项目的研究，对控制集理论做了一定的补充，获得了一些新的结果和算法。此外，在本项目的支持下，项目组成员还在生物信息领域做了一些工作，主要涉及到药物和化合物性质的预测、重要生物过程相关基因的鉴别等。