反馈集问题的研究进展

反馈集问题是经典的np难问题，在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用，按照反馈集中元素类型可分为反馈顶点集(fvs)问题和反馈边集(fas)问题。人们利用线性规划和局部搜索等技术设计了一系列关于fvs和fas问题的近似算法，并基于分枝一剪枝策略和加权分治技术提出了fvs问题的精确算法。随着参数计算理论的发展，近年来参数化反馈集问题引起了人们的重视，并取得了很大突破。目前已经证明了无向图和有向图中fvs问题和fas问题都是固定参数可解的(fpt)。利用树分解、分支搜索、迭代压缩等技术，对无向图fvs问题提出了一系列fpt算法。针对某些特殊的应用，人们开展了对具有特殊性质的图上fvs问题的研究，提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于fvs问题的近似算法与精确算法，然后具体分析了fvs问题的参数化算法。进一步阐述了关于有向图和特殊图上fvs问题的研究现状，介绍了fas问题的研究成果。基于对反馈集问题研究现状的分析，提出了今后fvs问题研究中值得关注的几个方面。