基于核心化技术的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.

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

在本课题基金的支持下，按照研究计划中的研究内容和技术路线进行了三年的研究工作，取得了较好的研究成果。三年来，本项目主要研究了若干NP难解问题的FPT算法和核心化算法。在Information and Computation、Theoretical Computer Science、FAW、COCOA等期刊和会议上发表学术论文9篇。在FPT算法研究中，主要研究了最多内部节点生成树问题、供需树的最小代价划分问题及(n, 3)-MAX SAT问题的参数算法。对于最多内部节点生成树问题，提出了时间复杂度为O(4^k)的FPT算法。对于供需树的最小代价划分问题，提出了时间复杂度为O* (2.828^k)的FPT算法。对于(n, 3)-MAX SAT问题，提出了时间复杂度分别为Q*(1.175^k)和Q*(1.194^n)的FPT算法，其中k是对于某一个赋值F中被满足的子句个数，而n是F中变量的个数。在核心化算法研究中，通过针对具体问题本身结构特性分析，提出了新的核心化规则，得到了关于这些问题的改进的核心化算法。如顶点覆盖问题、P2-packing问题、split图中的k-Vertex-Disjoint Path问题和k-path问题、供需树的最小代价划分问题、CMSR问题、G7图上的（连通）支配集问题和路径收缩问题以及Co-Path Set问题。对于顶点覆盖问题，首次提出了基于皇冠分解技术的核大小为2k的核心化算法。对于P2-packing问题，提出了核大小为5k的核心化算法。对于供需树的最小代价划分问题, 提出了核大小为O(k^2)的核心化算法。对于CMSR问题，提出了核大小为42k的核心化算法。对于G7图上的（连通）支配集问题、路径收缩问题以及Co-Path Set问题，分别提出了核大小分别为O(k^2)、3k+4和4k的核心化算法。对于split图中的k-Vertex-Disjoint Path问题和k-path问题，分别提出了核大小分别为4k和O(k^2)的核心化算法。本项目的研究丰富和发展了基于核心化的FPT算法设计技术，为实际应用中的难解问题的高效求解提供了更加广阔的思路。