基于深层局部搜索的核心化技术研究

With the rapid development of the economy, more and more computationally hard problems have emerged in various industries. Kernelization has been widely used in many fields as a preprocessing method for tackling computationally hard problems, due to its powerful ability to reduce the input size of the given instances of hard problems in polynomial time. As the key factor of the performance of kernelization algorithms, kernelization technique has been one of the hot topics in parameterized complexity. This project will deeply study the limitations of the current existing kernelization techniques, including Extreme Structure, Local Reduction, Crown Decomposition, and Multiple Expansion, in the design of some existing kernelization algorithms, explore the internal relationship between the Local Search method and these kernelization techniques, and based on these, integrate the idea of Deep Local Search into them, obtain the corresponding kernelization techniques based on Deep Local Search, design effective kernelization algorithms for some unsolved FPT problems. The research of this project will significantly complement and improve some existing kernelization techniques, and largely enhance the development of parameterized complexity. It also provides references for preprocessing of computationally hard problems in many fields, and promotes the development of related fields.

随着经济的迅速发展，各行各业涌现出越来越多的计算难解问题。作为计算难解问题的一种预处理手段，参数计算中的核心化算法能在多项式时间内有效降低问题实例的规模，因此在许多领域有着广泛的应用。核心化技术作为核心化算法性能优劣的关键因素，一直是参数计算领域的一个研究热点。本项目将深入研究极值结构、局部简化、皇冠分解以及多倍扩张技术在已有核心化算法设计中的局限性，发掘局部搜索方法与这些核心化技术的内在联系，并在此基础上将深层局部搜索的思想融入其中，得到相应的基于深层局部搜索的核心化技术，为一些待解决的FPT问题设计高效的核心化算法。本项目的研究将完善或改进已有的一些核心化技术，在一定程度上丰富和发展了参数计算理论，并为诸多领域计算难解问题的预处理提供借鉴，进而推动相应领域的发展。

随着经济的迅速发展，各行各业涌现出越来越多的计算难解问题。参数算法是用来求解NP-难解问题的新方法，它的发展引起了人们的极大兴趣。参数计算中的核心化算法作为计算难解问题的一种预处理手段，能在多项式时间内有效降低问题实例的规模，在生物信息学、计算机网络等诸多领域有着广泛的应用。而核心化技术作为核心化算法性能优劣的关键因素，也因核心化算法的广泛应用受到了许多研究学者的关注，一直是参数计算领域的一个研究热点。. 本项目针对一些采用极值结构技术、局部简化技术、皇冠分解技术和多倍扩张技术所设计核心化算法的NP难解问题展开，分析了这些核心化技术在已有核心化算法设计中的局限性，发掘深层局部搜索方法与这些技术之间的内在联系，并在此基础上将深层局部搜索的思想融入其中，通过利用深层局部搜索方法的优点来弥补这些核心化技术的局限性，为一些FPT 问题设计了高效的核心化算法，如P2-packing问题、Claw and Diamond Free边删除问题、对偶着色问题、Proper Interval Edge Deletion问题。此外，本项目还对一些NP难解问题提出了高效的求解算法，如MAX SAT问题、无线网络中可叠加数据的传输能耗问题、室内定位的建模问题、弦图重构相关问题、最多内部节点生成树问题。经过四年的研究，本项目组取得了较好的成绩，相关的研究成果以论文的形式发表在著名的理论计算机方面的国际期刊和会议上。本项目的研究完善或改进了已有的一些核心化技术，为一些待解决的FPT问题设计了高效的核心化算法。所提出的“基于深层局部搜索的核心化技术”在一定程度上丰富和发展了参数计算理论，为诸多领域计算难解问题的预处理提供了借鉴，为实际应用中的难解问题的高效求解提供了更加广阔的思路，具有较大的理论意义和应用价值。