面向图类增量问题的参数算法及其应用研究

As a new method dealing with NP-hard problems, parameterized theory and method has been successfully applied in many practical fields. Many researches have been done on incremental problems by applying parameterized computation methods, which has better advantage in solving problems in many fields. Many results have been presented under this research direction. However, many aspects of the research on incremental problems need to be further explored. In this project, we will study the parameterizd algorithms for incremental problems of graphs problems. Critical parameters for the complexity of the incremental problems are analyzed firstly. Then, the multivariate parameterized model of the incremental problems will be built, and the parameterized complexities of the multivariate models are studied. By studying the structure properties of the incremental problems, and based on editing operations and graph structure, new kernelization methods for incremental problems are studied. Based on the impact of editing operations on graph structure, new parameterized algorithm technique solving the graph incremental problems will be studied. Finally, we will apply the study on parameterized algorithms for incremental problems to solve the optimization problems in bioinformatics.

作为处理实际工程中难解问题的新手段，参数计算理论和方法已在许多领域都得到成功应用。基于参数计算的增量问题研究在诸多领域优化问题求解中显示出了较好的优势，人们得到了一些结果，但相关研究还处于起步阶段，需要进一步发展和完善。本项目面向图类增量问题，分析影响问题复杂性的关键参数，建立问题的多元参数模型，并分析各类增量问题的参数复杂性；从增量问题结构性质出发，提出图结构性质的增量问题新核心化方法；基于编辑操作对图结构的影响，提出适用于解决图类增量问题的新的算法技术，并将增量问题参数算法研究成果应用到生物信息学领域中优化问题求解中。本项目的研究将为求解图类增量问题提供有效的算法处理技术，推动相关领域的发展。

在本基金的支持下，本项目围绕难解编辑和子模式挖掘等重要增量问题开展研究，分析了问题的复杂性性，设计了问题的核心化和相关算法，并研究了相关理论与技术的应用。主要成果如下：（1）挖掘了影响各类难解编辑和子模式挖掘问题复杂性的关键参数，建立了相应的多元参数模型，解决了若干问题的公开复杂性；（2）分析了各类编辑操作对问题核心化的影响，提出了基于问题实例结构编辑的核心化技术；（3）挖掘了问题解空间结构与各类编辑操作之间的关系，提出了基于问题实例结构分解的参数算法设计技术；（4）应用相关理论和方法设计了生物信息学、计算机网络和聚类数据分析等领域中若干难解编辑和子模式挖掘问题的有效求解算法。