收藏切换
Computational Complexity of Feedback Set and Subset Feedback Set Problems: A Survey
收藏切换
Tian Bai, Mingyu Xiao*
Journal of Computer Research and Development | 2025, 62(1) : 104 - 118
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(1): 104-118
• Artificial Intelligence •
Computational Complexity of Feedback Set and Subset Feedback Set Problems: A Survey
Full
Tian Bai, Mingyu Xiao*
Affiliations
  • School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731
  • born in 1993. PhD. Student member of CCF. His main research interests include graph algorithms and computational complexity

    born in 1979. PhD, professor. Distinguished member of CCF. His main research interests include graph theory and graph algorithms, exact and parameterized algorithms, combinatorial optimization, and mechanism design and algorithmic game theory

About Author:

born in 1993. PhD. Student member of CCF. His main research interests include graph algorithms and computational complexity

born in 1979. PhD, professor. Distinguished member of CCF. His main research interests include graph theory and graph algorithms, exact and parameterized algorithms, combinatorial optimization, and mechanism design and algorithmic game theory

Published: 2025-01-01 doi: 10.7544/issn1000-1239.202330693
Outline
收藏切换

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.

feedback set problem  /  subset feedback set problem  /  graph theory  /  computational complexity  /  graph algorithms
白天, 肖鸣宇. 反馈集与子集反馈集问题的计算复杂性研究进展. 计算机研究与发展, 2025 , 62 (1) : 104 -118 . DOI: 10.7544/issn1000-1239.202330693
Tian Bai, Mingyu Xiao. Computational Complexity of Feedback Set and Subset Feedback Set Problems: A Survey[J]. Journal of Computer Research and Development, 2025 , 62 (1) : 104 -118 . DOI: 10.7544/issn1000-1239.202330693
Year 2025 volume 62 Issue 1
103
46
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202330693
  • Receive Date:2023-08-23
  • Online Date:2026-11-10
  • Published:2025-01-01
Article Data
Affiliations
History
  • Received:2023-08-23
  • Revised:2024-01-22
Affiliations
    School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330693
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT