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

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

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.