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

Bai Tian; Xiao Mingyu

doi:10.7544/issn1000-1239.202330693

Journal of Computer Research and Development > 2025 > 62(1): 104-118. > DOI: 10.7544/issn1000-1239.202330693 CSTR: 32373.14.issn1000-1239.202330693

Bai Tian, Xiao Mingyu. 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

Citation:

PDF (1121 KB)

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

Funds: This work was supported by the National Natural Science Foundation of China (62372095, 61972070).

More Information

Author Bio:
Bai Tian: born in 1993. PhD. Student member of CCF. His main research interests include graph algorithms and computational complexity

Xiao Mingyu: 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
Received Date: August 22, 2023
Revised Date: January 21, 2024
Available Online: October 17, 2024

Graphical Abstract

Abstract

Abstract

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

FullText(HTML)

References (82)

References

[1]	王建新,江国红,李文军,等. 反馈集问题的研究进展[J]. 计算机科学,2011,38(1):40−47 doi: 10.3969/j.issn.1002-137X.2011.01.008 Wang Jianxin, Jiang Guohong, Ling Wenjun, et al. Algorithms for feedback set problems: A survey[J]. Computer Science, 2011, 38(1): 40−47 (in Chinese) doi: 10.3969/j.issn.1002-137X.2011.01.008
[2]	Stephen H U. A study of asynchronous logical feedback networks, technical reports vol. 320[R]. Cambridge, MA: Massachusetts Institute of Technology, Research Laboratory of Electronics, 1957
[3]	Zhao Qiulan. Ranking tournaments with no errors[D]. Hong Kong: University of Hong Kong, 2017
[4]	Ailon N, Charikar M, Newman A. Aggregating inconsistent information: Ranking and clustering[J]. Journal of the ACM, 2008, 55(5): 1−27
[5]	Kunzmann A, Wunderlich H J. An analytical approach to the partial scan problem[J]. Journal of Electronic Testing, 1990, 1(2): 163−174 doi: 10.1007/BF00137392
[6]	Kim J L, Peled U N, Perepelitsa I, et al. Explicit construction of families of LDPC codes with no 4-cycles[J]. IEEE Transactions on Information Theory, 2004, 50(10): 2378−2388 doi: 10.1109/TIT.2004.834760
[7]	Park H, Hong S, No J S, et al. Design of multiple-edge protographs for QC LDPC codes avoiding short inevitable cycles[J]. IEEE Transactions on Information Theory, 2013, 59(7): 4598−4614 doi: 10.1109/TIT.2013.2250574
[8]	Minoura T. Deadlock avoidance revisited[J]. Journal of the ACM, 1982, 29(4): 1023−1048 doi: 10.1145/322344.322351
[9]	曹玖新,高庆清,夏蓉清,等. 社交网络信息传播预测与特定信息抑制[J]. 计算机研究与发展,2021,58(7):1490−1503 doi: 10.7544/issn1000-1239.2021.20200809 Cao Jiuxin, Gao Qingqing, Xia Rongqing, et al. Information propagation prediction and specific information suppression in social networks[J]. Journal of Computer Research and Development, 2021, 58(7): 1490−1503 (in Chinese) doi: 10.7544/issn1000-1239.2021.20200809
[10]	朱军,胡文波. 贝叶斯机器学习前沿进展综述[J]. 计算机研究与发展,2015,52(1):16−26 doi: 10.7544/issn1000-1239.2015.20140107 Zhu Jun, Hu Wenbo. Recent advances in Bayesian machine learning[J]. Journal of Computer Research and Development, 2015, 52(1): 16−26 (in Chinese) doi: 10.7544/issn1000-1239.2015.20140107
[11]	崔焕庆,吴哲辉. 并行程序Petri网模型的结构性质[J]. 计算机研究与发展,2007,44(12):2130−2135 doi: 10.1360/crad20071220 Cui Huanqing, Wu Zhehui. Structural properties of parallel program's Petri net model[J]. Journal of Computer Research and Development, 2007, 44(12): 2130−2135 (in Chinese) doi: 10.1360/crad20071220
[12]	Kemeny J G. Mathematics without numbers[J]. Daedalus, 1959, 88(4): 577−591
[13]	Dechter R. Enhancement schemes for constraint processing: Back-jumping, learning, and cutset decomposition[J]. Artificial Intelligence, 1990, 41(3): 273−312 doi: 10.1016/0004-3702(90)90046-3
[14]	Bar-Yehuda R, Geiger D, Naor J, et al. Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference[J]. SIAM Journal on Computing, 1998, 27(4): 942−959 doi: 10.1137/S0097539796305109
[15]	Kratsch S, Schweitzer P. Isomorphism for graphs of bounded feedback vertex set number[G]//LNCS 6139: Proc of the 12th Scandinavian Symp and Workshops on Algorithm Theory (SWAT). Berlin: Springer, 1995: 81−92
[16]	Karp R. Reducibility among combinatorial problem[C]//Proc of a Symp on the Complexity of Computer Computations. Berlin: Springer, 1972: 85–103
[17]	Even G, Naor J, Schieber B, et al. Approximating minimum feedback sets and multicuts in directed graphs[J]. Algorithmica, 1998, 20(2): 151−174 doi: 10.1007/PL00009191
[18]	Even G, Naor J, Zosin L. An 8-approximation algorithm for the subset feedback vertex set problem[J]. SIAM Journal on Computing, 2000, 30(4): 1231−1252 doi: 10.1137/S0097539798340047
[19]	Xiao Mingyu, Nagamochi H. An FPT algorithm for edge subset feedback edge set[J]. Information Processing Letters, 2012, 112(1/2): 5−9
[20]	Chitnis R, Cygan M, Hajiaghayi M, et al. Directed subset feedback vertex set is fixed-parameter tractable[J]. ACM Transactions on Algorithms, 2015, 11(4): 1−28
[21]	Iwata Y, Kobayashi Y. Improved analysis of highest-degree branching for feedback vertex set[J]. Algorithmica, 2021, 83(8): 2503−2520 doi: 10.1007/s00453-021-00815-w
[22]	Fomin F V, Gaspers S, Lokshtanov D, et al. Exact algorithms via monotone local search[J]. Journal of the ACM, 2019, 66(2): 1−23
[23]	Li J, Nederlof J. Detecting feedback vertex sets of size k in O^*(2.7^k) time[J]. ACM Transactions on Algorithms, 2022, 18(4): 1−26
[24]	Bafna V, Berman P, Fujito T. A 2-approximation algorithm for the undirected feedback vertex set problem[J]. SIAM Journal on Discrete Mathematics, 1999, 12(3): 289−297 doi: 10.1137/S0895480196305124
[25]	Chen Jianer, Liu Yang, Lu Songjian, et al. A fixed-parameter algorithm for the directed feedback vertex set problem[J]. Journal of the ACM, 2008, 55(5): 177−186
[26]	Razgon I. Computing minimum directed feedback vertex set in O^*(1.9977ⁿ)[C]//Proc of the 10th Italian Conf on Theoretical Computer Science. Singapore: World Scientific, 2007: 70−81
[27]	Seymour P D. Packing directed circuits fractionally[J]. Combinatorica, 1995, 15(2): 281−288 doi: 10.1007/BF01200760
[28]	Even G, Naor J, Schieber B, et al. Approximating minimum feedback sets and multi-cuts in directed graphs: Extended summary[G]//LNCS 920: Proc of the 4th Int Conf on Integer Programming and Combinatorial Optimization (IPCO). Berlin: Springer, 1995: 14−28
[29]	Lawler E. A comment on minimum feedback arc sets[J]. IEEE Transactions on Circuit Theory, 1964, 11(2): 296−297 doi: 10.1109/TCT.1964.1082291
[30]	Bodlaender H L, Fomin F V, Koster A M C A, et al. A note on exact algorithms for vertex ordering problems on graphs[J]. Theory of Computing Systems, 2012, 50(3): 420−432 doi: 10.1007/s00224-011-9312-0
[31]	Cygan M, Pilipczuk M, Pilipczuk M, et al. On multiway cut parameterized above lower bounds[J]. ACM Transactions on Computation Theory, 2013, 5(1): 1−11
[32]	Karger D R, Klein P, Stein C, et al. Rounding algorithms for a geometric embedding of minimum multiway cut[J]. Mathematics of Operations Research, 2004, 29(3): 436−461. doi: 10.1287/moor.1030.0086
[33]	Chen Li, Kyng R, Liu Y P, et al. Maximum flow and minimum-cost flow in almost-linear time[C]//Proc of the 63rd Annual Symp on Foundations of Computer Science (FOCS). Los Alamitos, CA: IEEE Computer Society, 2022: 612−623
[34]	Iwata Y, Yamaguchi Y, Yoshida Y. 0/1/all CSPs, half-integral A-path packing, and linear-time FPT algorithms[C]// Proc of the 59th IEEE Annual Symp on Foundations of Computer Science (FOCS). Los Alamitos, CA: IEEE Computer Society, 2018: 462−473
[35]	Even G, Naor J, Schieber B, et al. Approximating minimum subset feedback sets in undirected graphs with applications[J]. SIAM Journal on Discrete Mathematics, 2000, 13(2): 255−267 doi: 10.1137/S0895480195291874
[36]	Garg N, Vazirani V V, Yannakakis M. Multiway cuts in node weighted graphs[J]. Journal of Algorithms, 2004, 50(1): 49−61 doi: 10.1016/S0196-6774(03)00111-1
[37]	Chitnis R, Fomin F V, Lokshtanov D, et al. Faster exact algorithms for some terminal set problems[J]. Journal of Computer and System Sciences, 2017, 88(3): 195−207
[38]	Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. San Francisco, CA: W. H. Freeman, 1979: 191−192
[39]	Speckenmeyer E. Untersuchungen zum feedback vertex set problem in ungerichteten graphen[D]. Paderborn: Universität Paderborn, 1983
[40]	Ueno S, Kajitani Y, Gotoh S. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three[J]. Discrete Mathematics, 1988, 72(1/2/3): 355−360
[41]	Gabow H N, Stallmann M. Efficient algorithms for graphic matroid intersection and parity (extended abstract)[G]∥LNCS 194: Proc of the 12th Int Colloquium on Automata, Languages, and Programming (ICALP). Berlin: Springer, 1985: 210−220
[42]	Yannakais M. Node-and edge-deletion NP-complete problems[C]//Proc of the 10th Annual ACM Symp on Theory of Computing (STOC). New York: ACM, 1978: 253−264
[43]	Lucchesi C L, Younger D H. A minimax theorem for directed graphs[J]. Journal of the London Mathematical Society, 1978, 2(3): 369−374
[44]	Gabow H N. A framework for cost-scaling algorithms for submodular flow problems[C]//Proc of the 34th Annual Symp on Foundations of Computer Science (FOCS). Los Alamitos, CA: IEEE Computer Society, 1993: 449−458
[45]	Cavallaro von D. Hamiltonicity and the computational complexity of graph problems[D]. Berlin: Technische Universität Berlin, 2019
[46]	Appel K, Haken W. Every planar map is four colorable. Part I: Discharging[J]. Illinois Journal of Mathematics, 1977, 21(3): 429−490
[47]	Appel K, Haken W, Koch J. Every planar map is four colorable. Part II: Reducibility[J]. Illinois Journal of Mathematics, 1977, 21(3): 491−567
[48]	Robertson N, Sanders D P, Seymour P, et al. Efficiently four-coloring planar graphs[C]//Proc of the 28th Annual ACM Symp on Theory of Computing (STOC). New York: ACM, 1996: 571−575
[49]	Speckenmeyer E. On feedback problems in digraphs[G]//LNCS 484: Proc of the 15th Int Workshop of Graph-Theoretic Concepts in Computer Science (WG). Berlin: Springer. 1989: 218−231
[50]	Cai Maocheng, Deng Xiaotie, Zang Wenan. A min-max theorem on feedback vertex sets[J]. Mathematics of Operations Research, 2002, 27(2): 361−371 doi: 10.1287/moor.27.2.361.328
[51]	Alon N. Ranking tournaments[J]. SIAM Journal on Discrete Mathematics, 2006, 20(1): 137−142 doi: 10.1137/050623905
[52]	Charbit P, Thomasse S, Yeo A. The minimum feedback arc set problem is NP-hard for tournaments[J]. Combinatorics, Probability and Computing, 2007, 16(1): 1−4 doi: 10.1017/S0963548306007887
[53]	Conitzer V. Computing Slater rankings using similarities among candidates[C]//Proc of the 21st National Conf on Artificial Intelligence (AAAI). Palo Alto, CA: AAAI, 2006: 613−619
[54]	Guo Jong, Huffner F, Moser H. Feedback arc set in bipartite tournaments is NP-complete[J]. Information Processing Letters, 2007, 102(2/3): 62−65
[55]	Brandstädt A, Kratsch D. On the restriction of some NP-complete graph problems to permutation graphs[G]//LNCS 199: Proc of the Int Conf on Fundamentals of Computation Theory (FCT). Berlin: Springer, 1985: 53−62
[56]	Brandstädt A, Kratsch D. On domination problems for permutation and other graphs[J]. Theoretical Computer Science, 1987, 54(2/3): 181−198
[57]	Brandstädt A. On improved time bounds for permutation graph problems[G]//LNCS 657: Proc of the 18th Int Workshop Graph-Theoretic Concepts in Computer Science (WG). Berlin: Springer, 1992: 1−10
[58]	Liang Y D. On the feedback vertex set problem in permutation graphs[J]. Information Processing Letters, 1994, 52(3): 123−129 doi: 10.1016/0020-0190(94)00133-2
[59]	Honma H, Kitamura Y, Masuyama S. An algorithm for minimum feedback vertex set problem on a trapezoid graph[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2011, 94(6): 1381−1385
[60]	Takaoka A, Yayu S, Ueno S. On minimum feedback vertex sets in bipartite graphs and degree-constraint graphs[J]. IEICE Transactions on Information and Systems, 2013, 96(11): 2327−2332
[61]	Coorg S R, Rangan C P. Feedback vertex set on cocomparability graphs[J]. Networks, 1995, 26(2): 101−111 doi: 10.1002/net.3230260205
[62]	Liang Y D, Chang Mawshang. Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs[J]. Acta Informatica, 1997, 34(5): 337−346 doi: 10.1007/s002360050088
[63]	Gavril F. Minimum weight feedback vertex sets in circle n-gon graphs and circle trapezoid graphs[J]. Discrete Mathematics, Algorithms and Applications, 2011, 3(3): 323−336 doi: 10.1142/S1793830911001243
[64]	Papadopoulos C, Tzimas S. Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs[J]. Discrete Applied Mathematics, 2019, 258(4): 204−221
[65]	Yannakakis M, Gavril F. The maximum k-colorable subgraph problem for chordal graphs[J]. Information Processing Letters, 1987, 24(2): 133−137 doi: 10.1016/0020-0190(87)90107-4
[66]	Lu Chinlung, Tang Chuanyi. A linear-time algorithm for the weighted feedback vertex problem on interval graphs[J]. Information Processing Letters, 1997, 61(2): 107−111 doi: 10.1016/S0020-0190(96)00193-7
[67]	Fomin F V, Heggernes P, Kratsch D, et al. Enumerating minimal subset feedback vertex sets[J]. Algorithmica, 2014, 69(1): 216−231 doi: 10.1007/s00453-012-9731-6
[68]	Bai Tian, Xiao Mingyu. Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs[G]//LNCS 13571: Proc of the 17th Annual Conf on Theory and Applications of Models of Computation (TAMC). Berlin: Springer, 2023: 249−261
[69]	Marathe M V, Ravi R, Rangan C P. Generalized vertex covering in interval graphs[J]. Discrete Applied Mathematics, 1992, 39(1): 87−93 doi: 10.1016/0166-218X(92)90116-R
[70]	Kratsch D, Muller H, Todinca I. Feedback vertex set on AT-free graphs[J]. Discrete Applied Mathematics, 2008, 156(10): 1936−1947 doi: 10.1016/j.dam.2007.10.006
[71]	Poljak S. A note on stable sets and colorings of graphs[J]. Commentationes Mathematicae Niversitatis Carolinae, 1974, 15(2): 307−309
[72]	Munaro A. On line graphs of subcubic triangle-free graphs[J]. Discrete Mathematics, 2017, 340(6): 1210−1226 doi: 10.1016/j.disc.2017.01.006
[73]	Chiarelli N, Hartinger T R, Johnson M, et al. Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity[J]. Theoretical Computer Science, 2018, 705: 75−83 doi: 10.1016/j.tcs.2017.09.033
[74]	Dabrowski K K, Fehali C, Johnson M, et al. On cycle transversals and their connected variants in the absence of a small linear forest[J]. Algorithmica, 2020, 82(10): 2841−2866 doi: 10.1007/s00453-020-00706-6
[75]	Abrishami T, Chudnovsky M, Pilipczuk M, et al. Induced subgraphs of bounded treewidth and the container method[C]//Proc of the 2021 ACM-SIAM Symp on Discrete Algorithms (SODA). Philadelphia, PA: SIAM, 2021: 1948−1964
[76]	Paesani G, Paulusma D, Rzazwski P. Feedback vertex set and even cycle transversal for H-free graphs: Finding large block graphs[J]. SIAM Journal on Discrete Mathematics, 2022, 36(4): 2453−2472 doi: 10.1137/22M1468864
[77]	Paesani G, Paulusma D, Rzazwski P. Classifying subset feedback vertex set for H-free graphs[G]//LNCS 13453: Proc of the 48th Int Workshop Graph-Theoretic Concepts in Computer Science (WG). Berlin: Springer, 2022: 412−424
[78]	Jiang Wei, Liu Tian, Xu Ke. Tractable feedback vertex sets in restricted bipartite graphs[G]//LNCS 6831: Proc of the 5th Int Conf Combinatorial Optimization and Applications (COCOA). Berlin: Springer, 2011: 424−434
[79]	Jiang Wei, Liu Tian, Ren Tienan, et al. Two hardness results on feedback vertex sets[G]//LNCS 6681: Proc of Joint Int Conf on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM). Berlin: Springer, 2011: 233−243
[80]	Kloks T, Liu Chinghao, Poon Sheunghung. Feedback vertex set on chordal bipartite graphs[J]. arXiv preprint, arXiv: 1104.3915, 2011
[81]	Jiang Wei, Liu Tian, Wang Chaoyi, et al. Feedback vertex sets on restricted bipartite graphs[J]. Theoretical Computer Science, 2013, 507: 41−51 doi: 10.1016/j.tcs.2012.12.021
[82]	Liu Tian, Lu Min, Lu Zhao, et al. Circular convex bipartite graphs: Feedback vertex sets[J]. Theoretical Computer Science, 2014, 556: 55−62 doi: 10.1016/j.tcs.2014.05.001

[1]	Guo Yaqing, Wang Wenjian, Su Meihong. An Adaptive Regression Feature Selection Method for Datasets with Outliers[J]. Journal of Computer Research and Development, 2019, 56(8): 1695-1707. DOI: 10.7544/issn1000-1239.2019.20190313
[2]	Xu Hang, Zhang Kai, Wang Wenjian. A Feature Selection Method for Small Samples[J]. Journal of Computer Research and Development, 2018, 55(10): 2321-2330. DOI: 10.7544/issn1000-1239.2018.20170748
[3]	Wang Ling, Meng Jianyao. Dynamic Fuzzy Features Selection Based on Variable Weight[J]. Journal of Computer Research and Development, 2018, 55(5): 893-907. DOI: 10.7544/issn1000-1239.2018.20170503
[4]	Yao Sheng, Xu Feng, Zhao Peng, Ji Xia. Intuitionistic Fuzzy Entropy Feature Selection Algorithm Based on Adaptive Neighborhood Space Rough Set Model[J]. Journal of Computer Research and Development, 2018, 55(4): 802-814. DOI: 10.7544/issn1000-1239.2018.20160919
[5]	Dong Hongbin, Teng Xuyang, Yang Xue. Feature Selection Based on the Measurement of Correlation Information Entropy[J]. Journal of Computer Research and Development, 2016, 53(8): 1684-1695. DOI: 10.7544/issn1000-1239.2016.20160172
[6]	Xu Junling, Zhou Yuming, Chen Lin, Xu Baowen. An Unsupervised Feature Selection Approach Based on Mutual Information[J]. Journal of Computer Research and Development, 2012, 49(2): 372-382.
[7]	Jing Hongfang, Wang Bin, YangYahui, Xu Yan. Category Distribution-Based Feature Selection Framework[J]. Journal of Computer Research and Development, 2009, 46(9): 1586-1593.
[8]	Gao Jun, Wang Shitong, Deng Zhaohong. GPSFM: Generalized Potential Support Features Selection Method[J]. Journal of Computer Research and Development, 2009, 46(1): 41-51.
[9]	Xu Yan, Li Jintao, Wang Bin, Sun Chunming, Zhang Sen. A Study on Constraints for Feature Selection in Text Categorization[J]. Journal of Computer Research and Development, 2008, 45(4): 596-602.
[10]	Liu Tao, Wu Gongyi, Chen Zheng. An Effective Unsupervised Feature Selection Method for Text Clustering[J]. Journal of Computer Research and Development, 2005, 42(3).