基于结构分解的图类难解问题核心化及参数算法研究

Gallai-Edmond decomposition and modular decomposition methods have been paid lots of attention in parameterized computation field. Based on Gallai-Edmond decomposition and modular decomposition, lots of kernelization results and parameterized algorithms have been proposed for hard problems. However, many aspects of the study on Gallai-Edmond decomposition and modular decomposition in parameterized computation are not profound, and need more efforts to develop. This project will focus on graph hard problems. Firstly, based on the structure properties of Gallai-Edmond decomposition and modular decomposition, we will build connection between graph decomposition structure and solution structure of problems. Secondly, by the study on the structure properties of Gallai-Edmond decomposition and modular decomposition, we study the kernelization and parameterized algorithms for graph hard problems, such as Bisection related problems, Induced Matching related problems, Konig graph related problems, etc. Finally, by combing current parameterized techniques with graph decomposition methods, we will study new techniques to develop kernelization and parameterized algorithms for hard problems. This project will provide new methods to deal with hard problems in many application fields, and promote the development of related fields.

Gallai-Edmond分解和模块分解两种图分解方法已在参数计算领域受到了广泛的关注。基于Galai-Edmond分解和模块分解，人们提出了许多难解问题的核心化和参数算法结果，但许多方面的研究还处于起步阶段，需要进一步丰富和发展。本项目面向Bisection类问题、Induced Matching相关问题、Konig图相关问题等图类难解问题，从Gallai-Edmond分解和模块分解本身的结构特性出发，建立图分解结构与问题解空间结构的关联关系，提出基于Gallai-Edmond分解和模块分解结构的核心化方法和参数算法，并结合经典的参数算法设计技术，研究相应技术与Gallai-Edmond分解、模块分解在图类难解问题求解中的综合应用，为应用领域中难解问题求解提供新的方法，继而推动相关应用领域的发展。

图分解方法是一种有效的图预处理技术，可以在多项式时间内对任意图给出具有某种特定性质的结构分解，为参数计算领域中图类难解问题的求解提供重要理论基础。本项目从若干经典图类难解问题出发，分析了各类参数对图分解问题的影响，结合相应的多元参数模型与复杂性证明，提出基于实例结构的参数化方法，重点研究了图分解结构与问题解空间结构的关系研究、基于图分解的核心化方法研究、基于图分解的参数算法研究、图分解技术与其它参数算法设计技术的结合应用研究。本项目取得的主要研究成果如下：1. 通过多元参数下的复杂性分析方法，建立了若干图类难解问题的多元参数模型和复杂性证明；2. 通过基于Gallai-Edmond分解和模块分解方法和图的模式匹配，提出了基于问题实例结构的分解结构核心化技术，得到了一系列的核心化结果，保持着若干问题的当前最好核心化结果；3. 通过挖掘问题解空间结构与各类参数之间的关系，提出了基于问题实例结构进行图分解的参数算法和近似算法设计技术，得到了一系列的参数算法结果，保持着若干问题的当前最好参数算法和近似算法结果。4. 基于图分解核心化方法与图分解参数算法设计技术，分析了生物信息学、数据聚类等领域中的若干图类难解问题和图分解参数化问题，设计了相应的参数算法和近似算法求解方法；在本项目的资助下，本课题组共发表了学术论文26篇。共培养博士、硕士研究生9人。本项目的实施对图类难解问题的参数化求解有着重要的参考价值，同时对生物信息学和数据聚类领域中的图类难解问题研究有重要的指导意义。