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
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.
| 科 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 |