参数计算中树分解方法及其应用研究

作为有效求解难解问题的手段，树分解方法受到了人们广泛的关注。各领域中的诸多难解问题基于树分解技术得到有效求解，如概率网络、生物信息学等。树分解方法逐步成为人们研究的热点，但树分解许多方向的研究正处于起步阶段，都待进一步发展和完善。. 本项目将树分解方法进行深入研究，首先研究树分解求解算法，以提高求解树分解的效率。然后直接面向各领域的具体问题，研究树分解与其它参数算法技术的结合应用，并基于此，从树分解规约技术角度研究新的求解难解问题的方法。最后，以生物信息学为实际应用领域，研究树分解在生物信息学难解问题求解中的应用。本项目的研究旨在建立系统的应用树分解求解难解问题的方法，为应用领域中的难解问题求解提供新的思路，提高问题的求解效率，继而推动相关应用领域的发展。

在本课题基金的支持下，按照研究计划中的研究内容和技术路线进行了三年的研究工作，取得了较好的研究成果。综合三年来的工作，在本基金的资助下，我们在主要研究了树分解技术的应用，树结构相关问题的参数算法和核心化，以及若干难解问题的参数算法和核心化研究，并把树分解理论及其参数计算理论应用于计算机网络、社会学和生物信息学中。对树分解及树状结构的参数算法研究中，本项目主要研究了基于树分解的符号支配集问题参数算法、直角线段的路径覆盖问题、最大一致森林问题的参数算法、路径覆盖和星形覆盖一棵树问题和最大内部节点生成树近似算法。对树分解的符号支配集问题给出时间复杂度为O(k^k0.5)参数算法,对直角线段覆盖问题给出大小为O((2d)k)的核及二维上时间复杂度为O(3k)的参数算法，对最大一致森林问题分别为有根和无根的多颗二叉树给出时间复杂度为O(3k)和O(4k)的算法，对于路径覆盖和星形覆盖问题，分别给出时间复杂度为O((2+c)k)和O(4k)的参数算法，其中星形覆盖的核为O(k3)，最后对于最大内部节点生成树，给出近似比为1.5的近似算法。项目对其他一些NP难解问题的核心化及参数算法也进行了研究，为它们提出来若干有效的归约规则和高效的参数算法，例如加权的3-set Packing、正负支配集和 P2-packing等问题都给出了不错的结果。对于加权的3-set Packing给出了O(k3)的核，对正负支配集问题给出一个亚指数的算法，以及P2-packing问题大小为O(k2)的核和O(8k)的参数算法。最后项目将参数计算推广到实际应用中，取得了一系类成果。其中项目主要针对传感器网络和社交网络中的参数应用进行了研究，如无线传感器网路的Max- lifetime Target Coverage问题以及d-approval规则投票系统等问题。项目为其建立模型，设计近似算法，参数算法以及随机算法。对Max- lifetime Target Coverage问题，项目证明Max-min Target Coverage是FPT的，而对d-approval规则投票系统问题，项目给出大小为O(kd+2)的核。.此项目的研究不仅对参数理论未来的发展起到极大的促进作用，同时也推动了用参数计算理论来求解实际问题的步伐.