难解问题的核心化技术及其应用研究

在计算机科学领域，许多问题都因海量数据的输入，在求解时往往陷入了计算难解的困境。如何有效处理问题的实例规模以实现对问题有效求解已成为人们关注的研究热点。作为有效降低问题规模的算法预处理技术，核心化受到了人们广泛的关注，但核心化目前的发展还处在一个初级阶段，许多方面的研究才刚刚起步，亟待进一步丰富和发展。. 本项目通过研究问题解空间与问题规模的内在联系、问题核存在性的判定、问题核下界分析技术、问题核与问题求解算法的关系等方面，旨在提出新的核心化设计与分析技术，有效降低问题的规模，并把核心化应用到计算机网络、生物信息计算等具体应用领域中，为这些领域中问题的求解提供新的预处理方法，继而推动相关领域的发展。

在本基金的支持下，课题组对NP-难问题的核心化算法、参数算法的设计以及应用进行了深入的研究，并且取得了很大进展。在核心化算法的设计方面，通过对平面图结构的深入分析，我们提出了顶点划分技术。此方法相比区域分解技术，可更简单有效的分析平面图上若干问题的核。基于此顶点划分技术，能较大改进平面图上满足小常数距离性质的一些问题的核大小。例如，分别对Connected Vertex Cover问题、Edge Dominating Set问题、Maximum Triangle Packing问题和Connected Dominating Set问题进行了研究，并提出了对应的核心化算法，其核的大小分别为4k、12k、75k和130k，改进了之前的相应的最小的核，其大小分别为14k、28k、624k和413k。在参数算法的设计方面，基于参数计算基础理论，对若干 NP 难问题的固定参数算法进行了深入研究，并提出相应改进的参数算法。例如，分别对于3-Set Packing问题、rD-Matching问题、P2-Packing问题、Cograph Editing问题进行了的研究，并提出了时间复杂度为O*(3.53^{3k})、O*(4^{(r-1)^k+o(k)})、O*(8^k)和O*(4.612^k)的参数算法，改进了之前最好的参数算法，其时间复杂度分别为O*(4.61^{3k})、O*(4^{rk+o(k)})、O*(14.67^k)和O*(6^k)。在参数计算理论应用方面，将参数计算理论应用到了实际生活的诸多方面，如计算机网络和生物信息学等。例如，对于无线自组网络中的Min-power multicast问题，证明了相关问题的参数复杂性，并提出了相关的参数算法。此外，对生物信息学中的蛋白质复合物挖掘、网络基序发现和关键蛋白质预测等生物计算问题进行了深入的研究，并取得了一系列在国际上有影响的成果。.此项目的研究不仅对参数理论未来的发展起到极大的促进作用，同时也推动了用参数计算理论来求解实际问题的步伐。