基于核心化技术的FPT算法研究

固定参数可解（FPT）算法是参数计算及复杂性理论的重要组成部分。由于在生物信息学、计算机网络等诸多领域的广泛应用，FPT算法的设计受到了越来越多的研究学者的关注，并成为理论计算机科学领域的一个研究热点。. 核心化技术主要用来设计核心化算法，人们很少用其设计FPT算法。因为核心化不但可以减小问题解搜索空间的大小而且可以改变问题解搜索空间的结构，所以核心化技术可以用来设计高效的FPT算法。本项目将研究基于核心化技术的FPT算法。具体地，本项目将针对一些具体的难解问题，深入分析核心化技术的基本思想与问题的结构特性之间的关系，利用核心化技术为其设计高效的FPT算法，进而丰富和发展基于核心化的FPT算法设计技术，为实际应用中的难解问题的高效求解提供更加广阔的思路，对相关应用领域的发展起到推动作用。

Fixed parameterized tractable (FPT) algorithm is an important component of Parameterized Computation and Complexity Theory. For the wide applications in the fields of bioinformatics, computer networks and so on, designing FPT algorithms has attracted more and more researchers' attentions, and it becomes a hot research topic in the field of theoretical computer science. . kernelization techniques are mainly used to design kernelization algorithms, and they are rarely used in designing FPT algorithms. Since kernelization can not only decrease the size of solution search space for the problem, but also change its structure, kernelization techniques can be used to design efficient FPT algorithms. This proposed project will be focused on the FPT algorithms based on kernelization techniques. More precisely, as to some specific hard problems, this project will investigate the relationship between the main idea of kernelization techniques and the structure properties of the problems, and design efficient FPT algorithms for them by kernelization techniques, and then enrich and develop the FPT algorithms design techniques based on kernelization. Moreover, this project will provide broad-mind for efficient resolution for hard problems in the practical applications, and promote the development of corresponding areas.