精确计算和参数计算的算法新技术

精确算法和参数算法是近二十年来发展起来的用以求解NP-难问题的方法，它引起了人们广泛的关注。为了进一步推广精确算法和参数算法在实际中的应用，开发用来设计更加快速的精确算法和参数算法的新技术就显得尤为重要。本项目将从新的角度研究精确计算和参数计算的算法新技术，并将这些技术应用到求解许多重要NP-难问题的过程中。本项目研究内容主要包括：（1）从一些具体的经典NP-难问题出发，挖掘出它们的新的量度；（2）基于图分割和组合对偶，开发出新的核心化技术；（3）结合已有的代数知识，开发新的代数技术，用以设计精确算法和参数算法。.本项目的研究成果将对如何设计高效的精确算法和参数算法起到重要作用，并对求解实际应用中的难解问题有着重大的意义。

在本课题基金的支持下，按照研究计划中的研究内容和技术路线进行了四年的研究工作，取得了较好的研究成果。综合四年来的工作，在本基金的资助下，我们在主要研究了若干难解问题的参数算法和核心化研究，并把参数计算理论应用于计算机网络、社会学和生物信息学中。在IEEE Transactions on Computers、Theoretical Computer Science、Journal of Combinatorial Optimization、 ESA、WADS、COCOON等期刊和会议上发表学术论文28篇。在参数算法研究中，主要研究了符号支配集问题参数算法、直角线段的路径覆盖问题、最大一致森林问题的参数算法、路径覆盖和星形覆盖一棵树问题和最大内部节点生成树近似算法。对树分解的符号支配集问题给出时间复杂度为O(k^k0.5)参数算法。对直角线段覆盖问题给出大小为O((2d)k)的核，对最大一致森林问题分别为有根和无根的多颗二叉树给出时间复杂度为O(3^k)和O(4^k)的算法，对于路径覆盖和星形覆盖问题，分别给出时间复杂度为O((2+c)^k)和O(4^k)的参数算法，其中星形覆盖的核为O(k^3)，最后对于最大内部节点生成树，给出近似比为1.5的近似算法。本课题组还对其它一些NP难解问题的核心化及参数算法进行了研究，提出了若干有效的归约规则和高效参数算法，例如加权3-set Packing、正负支配集和 P2-packing等问题。对于加权的3-set Packing给出了O(k^3)的核，对正负支配集问题给出一个亚指数的算法，以及P2-packing问题大小为O(k^2)的核和O(8^k)的参数算法。本课题组还将参数计算推广到实际应用中，取得了一系类成果。针对传感器网络和社交网络中的难解问题进行了研究，如无线传感器网网络的Max- lifetime Target Coverage问题、d-approval规则投票系统等问题。对于Max- lifetime Target Coverage问题，证明了该问题是FPT的。针对d-approval规则投票系统问题，给出了大小为O(k^(d+2))的核。课题组在此方面的研究不仅推进了参数计算理论的发展，同时也推动了参数计算理论及技术在实际领域的应用。