反馈集与子集反馈集问题的计算复杂性研究进展  

Computational Complexity of Feedback Set and Subset Feedback Set Problems:A Survey

作　　者：白天 肖鸣宇 Bai Tian;Xiao Mingyu(School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731)

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《计算机研究与发展》2025年第1期104-118,共15页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(62372095,61972070)。

摘　　要：反馈集问题(feedback set problem)是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用.子集反馈集问题(subset feedback set problem)是反馈集问题的一种更一般化的形式,更加具有普适性和实用性.近年来,这2个问题在计算复杂性上的分类工作已逐步完善,在算法领域也已出现许多重要的突破.相关研究工作分为2个部分进行介绍.第1部分详尽地介绍了反馈集和子集反馈集各种不同版本的问题,梳理了它们之间的一些重要关系,并介绍了这些问题在一般图上的计算复杂性.第2部分系统性地介绍了反馈集和子集反馈集问题在一些重要子图类上的计算复杂性,包括度有界的图类、平面图类、竞赛图图类、相交图类、禁止图图类和二部图图类.最后对反馈集和子集反馈集问题的研究现状进行分析和总结,概括了目前主流的研究趋势.The feedback set problem is one of the most widely and deeply studied NP-complete graph problems in the field of computer science,with important applications in concurrent computing,large-scale integrated circuits,coding design,software verification,and social network analysis.The subset feedback set problem is a nature generalization of the feedback set problem,and has much universal and practical.In recent several years,the classification of the computational complexity for these two problems has drawn certain interests,and many breakthroughs have been made in the area of algorithms.In this paper,the survey on these problems mainly contains two parts.The first part introduces different versions of the feedback set and subset feedback set problems.The essential relations among these versions and their computational complexity in general graphs are also discussed in this part.The second part introduces the computational complexity of the feedback set and subset feedback set problems in some important and classical graph subclasses,including degree bounded graphs,planar graphs,tournaments,intersection graphs,forbidden graphs,and bipartite graphs.Finally,by analyzing and summarizing the existing research,the major research trends on the feedback set and subset feedback set problems are outlined.

关 键 词：反馈集问题 子集反馈集问题 图论 计算复杂性 图算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]