Article(id=1327011514155905155, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327011511924535414, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202330693, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1692720000000, receivedDateStr=2023-08-23, revisedDate=1705852800000, revisedDateStr=2024-01-22, acceptedDate=null, acceptedDateStr=null, onlineDate=1794313799655, onlineDateStr=2026-11-10, pubDate=1735660800000, pubDateStr=2025-01-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794313799655, onlineIssueDateStr=2026-11-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794313799655, creator=13701087609, updateTime=1794313799655, updator=13701087609, issue=Issue{id=1327011511924535414, tenantId=1146029695717560320, journalId=1324759914146529478, year='2025', volume='62', issue='1', pageStart='1', pageEnd='283', issueExtLink='null', onlineDate='null', pubDate='1735660800000', pubDateStr='2025-01-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794313799123, creator='13701087609', updateTime=1794376660021, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1327275170160554491, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327011511924535414, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1327275170160554492, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327011511924535414, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=104, endPage=118, ext={EN=ArticleExt(id=1327011516085284996, articleId=1327011514155905155, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Computational Complexity of Feedback Set and Subset Feedback Set Problems: A Survey, columnId=1325489891789910943, journalTitle=Journal of Computer Research and Development, columnName=Artificial Intelligence, runingTitle=null, highlight=null, articleAbstract=
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.
, authors=Tian Bai, Mingyu Xiao*, authorsList=Tian Bai, Mingyu Xiao, authorCompany=null, correspAuthors=Mingyu Xiao, authorNote=
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
, correspAuthorsNote=null, copyrightStatement=Copyright © 2025 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1327011517465211025, articleId=1327011514155905155, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=反馈集与子集反馈集问题的计算复杂性研究进展, columnId=1325489892104483745, journalTitle=计算机研究与发展, columnName=人工智能, runingTitle=null, highlight=null, articleAbstract=
反馈集问题(feedback set problem)是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用. 子集反馈集问题(subset feedback set problem)是反馈集问题的一种更一般化的形式,更加具有普适性和实用性. 近年来,这2个问题在计算复杂性上的分类工作已逐步完善,在算法领域也已出现许多重要的突破. 相关研究工作分为2个部分进行介绍. 第1部分详尽地介绍了反馈集和子集反馈集各种不同版本的问题,梳理了它们之间的一些重要关系,并介绍了这些问题在一般图上的计算复杂性. 第2部分系统性地介绍了反馈集和子集反馈集问题在一些重要子图类上的计算复杂性,包括度有界的图类、平面图类、竞赛图图类、相交图类、禁止图图类和二部图图类. 最后对反馈集和子集反馈集问题的研究现状进行分析和总结,概括了目前主流的研究趋势.
, authors=白天, 肖鸣宇*, authorsList=白天, 肖鸣宇, authorCompany=null, correspAuthors=肖鸣宇, authorNote=
 |
1993年生. 博士. CCF学生会员. 主要研究方向为图算法与计算复杂性 |
 |
1979年生. 博士,教授. CCF杰出会员. 主要研究方向为图论与图算法、精确与参数算法、组合优化、机制设计与算法博弈论 |
, correspAuthorsNote=
, copyrightStatement=版权所有 © 2025 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=m+gvniOkM3IYGCk630KVvg==, magXml=e7E93w5EE5zK1dzghC4dJQ==, pdfUrl=null, pdf=lM2AHquc0/kQwdDFbeFXmQ==, pdfFileSize=1148004, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=VTNPYsw9OvQvCVPD1LCGuA==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=nhIZYfpVh8K0b4r48gmpzw==, mapNumber=null, fund=null)}, authors=[Author(id=1327011965605622337, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=tianbai@std.uestc.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327011965672731203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, authorId=1327011965605622337, language=EN, stringName=Tian Bai, firstName=Tian, middleName=null, lastName=Bai, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, bio={"content":"
born in 1993. PhD. Student member of CCF. His main research interests include graph algorithms and computational complexity
"}, bioImg=null, bioContent=
born in 1993. PhD. Student member of CCF. His main research interests include graph algorithms and computational complexity
, aboutCorrespAuthor=null), CN=AuthorExt(id=1327011965752422980, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, authorId=1327011965605622337, language=CN, stringName=白天, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=电子科技大学计算机科学与工程学院 成都 611731, bio={"img":"orTYlm80S82r7Jix3IMxdg==","content":"
1993年生. 博士. CCF学生会员. 主要研究方向为图算法与计算复杂性
"}, bioImg=orTYlm80S82r7Jix3IMxdg==, bioContent=
1993年生. 博士. CCF学生会员. 主要研究方向为图算法与计算复杂性
, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327011965521736253, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, xref=null, ext=[AuthorCompanyExt(id=1327011965530124862, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, companyId=1327011965521736253, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731), AuthorCompanyExt(id=1327011965538513471, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, companyId=1327011965521736253, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=电子科技大学计算机科学与工程学院 成都 611731)])]), Author(id=1327011965823726150, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=myxiao@uestc.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327011965903417928, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, authorId=1327011965823726150, language=EN, stringName=Mingyu Xiao, firstName=Mingyu, middleName=null, lastName=Xiao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, bio={"content":"
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
"}, bioImg=null, bioContent=
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
, aboutCorrespAuthor=null), CN=AuthorExt(id=1327011965974721097, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, authorId=1327011965823726150, language=CN, stringName=肖鸣宇, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=电子科技大学计算机科学与工程学院 成都 611731, bio={"img":"mtkDw/ovhCn62I74ScjLoA==","content":"
1979年生. 博士,教授. CCF杰出会员. 主要研究方向为图论与图算法、精确与参数算法、组合优化、机制设计与算法博弈论
"}, bioImg=mtkDw/ovhCn62I74ScjLoA==, bioContent=
1979年生. 博士,教授. CCF杰出会员. 主要研究方向为图论与图算法、精确与参数算法、组合优化、机制设计与算法博弈论
, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327011965521736253, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, xref=null, ext=[AuthorCompanyExt(id=1327011965530124862, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, companyId=1327011965521736253, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731), AuthorCompanyExt(id=1327011965538513471, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, companyId=1327011965521736253, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=电子科技大学计算机科学与工程学院 成都 611731)])])], keywords=[Keyword(id=1327011966138298954, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, orderNo=1, keyword=feedback set problem), Keyword(id=1327011966238962251, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, orderNo=2, keyword=subset feedback set problem), Keyword(id=1327011966327042636, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, orderNo=3, keyword=graph theory), Keyword(id=1327011966398345805, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, orderNo=4, keyword=computational complexity), Keyword(id=1327011966461260366, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, orderNo=5, keyword=graph algorithms), Keyword(id=1327011966528369231, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, orderNo=1, keyword=反馈集问题), Keyword(id=1327011966591283792, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, orderNo=2, keyword=子集反馈集问题), Keyword(id=1327011966654198353, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, orderNo=3, keyword=图论), Keyword(id=1327011966725501522, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, orderNo=4, keyword=计算复杂性), Keyword(id=1327011966788416083, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, orderNo=5, keyword=图算法)], refs=[Reference(id=1327011970886251116, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=王建新,江国红,李文军,等. 反馈集问题的研究进展[J]. 计算机科学,2011,38(1):40−47, articleTitle=null, refAbstract=null), Reference(id=1327011970982720109, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=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), articleTitle=null, refAbstract=null), Reference(id=1327011971095966318, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011971158880879, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhao Qiulan. Ranking tournaments with no errors[D]. Hong Kong: University of Hong Kong, 2017, articleTitle=null, refAbstract=null), Reference(id=1327011971230184048, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Ailon N, Charikar M, Newman A. Aggregating inconsistent information: Ranking and clustering[J]. Journal of the ACM, 2008, 55(5): 1−27, articleTitle=null, refAbstract=null), Reference(id=1327011971293098609, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Kunzmann A, Wunderlich H J. An analytical approach to the partial scan problem[J]. Journal of Electronic Testing, 1990, 1(2): 163−174, articleTitle=null, refAbstract=null), Reference(id=1327011971368596082, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011971435704947, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011971490230900, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Minoura T. Deadlock avoidance revisited[J]. Journal of the ACM, 1982, 29(4): 1023−1048, articleTitle=null, refAbstract=null), Reference(id=1327011971565728373, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=曹玖新,高庆清,夏蓉清,等. 社交网络信息传播预测与特定信息抑制[J]. 计算机研究与发展,2021,58(7):1490−1503, articleTitle=null, refAbstract=null), Reference(id=1327011971624448630, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=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), articleTitle=null, refAbstract=null), Reference(id=1327011971716723319, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=朱军,胡文波. 贝叶斯机器学习前沿进展综述[J]. 计算机研究与发展,2015,52(1):16−26, articleTitle=null, refAbstract=null), Reference(id=1327011973390250616, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhu Jun, Hu Wenbo. Recent advances in Bayesian machine learning[J]. Journal of Computer Research and Development, 2015, 52(1): 16−26 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327011973469942393, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=崔焕庆,吴哲辉. 并行程序Petri网模型的结构性质[J]. 计算机研究与发展,2007,44(12):2130−2135, articleTitle=null, refAbstract=null), Reference(id=1327011973537051258, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=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), articleTitle=null, refAbstract=null), Reference(id=1327011973620937339, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Kemeny J G. Mathematics without numbers[J]. Daedalus, 1959, 88(4): 577−591, articleTitle=null, refAbstract=null), Reference(id=1327011973709017724, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Dechter R. Enhancement schemes for constraint processing: Back-jumping, learning, and cutset decomposition[J]. Artificial Intelligence, 1990, 41(3): 273−312, articleTitle=null, refAbstract=null), Reference(id=1327011973805486717, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011973927121534, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011974057144959, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Karp R. Reducibility among combinatorial problem[C]//Proc of a Symp on the Complexity of Computer Computations. Berlin: Springer, 1972: 85–103, articleTitle=null, refAbstract=null), Reference(id=1327011974199751296, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Even G, Naor J, Schieber B, et al. Approximating minimum feedback sets and multicuts in directed graphs[J]. Algorithmica, 1998, 20(2): 151−174, articleTitle=null, refAbstract=null), Reference(id=1327011974476575361, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011974669513346, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Xiao Mingyu, Nagamochi H. An FPT algorithm for edge subset feedback edge set[J]. Information Processing Letters, 2012, 112(1/2): 5−9, articleTitle=null, refAbstract=null), Reference(id=1327011974862451331, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011975021834884, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Iwata Y, Kobayashi Y. Improved analysis of highest-degree branching for feedback vertex set[J]. Algorithmica, 2021, 83(8): 2503−2520, articleTitle=null, refAbstract=null), Reference(id=1327011975172829829, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011975390933638, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011975550317191, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011975663563400, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011975768421001, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Razgon I. Computing minimum directed feedback vertex set in O*(1.9977n)[C]//Proc of the 10th Italian Conf on Theoretical Computer Science. Singapore: World Scientific, 2007: 70−81, articleTitle=null, refAbstract=null), Reference(id=1327011975915221642, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Seymour P D. Packing directed circuits fractionally[J]. Combinatorica, 1995, 15(2): 281−288, articleTitle=null, refAbstract=null), Reference(id=1327011976020079243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011976175268492, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Lawler E. A comment on minimum feedback arc sets[J]. IEEE Transactions on Circuit Theory, 1964, 11(2): 296−297, articleTitle=null, refAbstract=null), Reference(id=1327011977504862862, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011977580360335, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011977651663504, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=35, authorNames=null, journalName=null, refType=null, unstructuredReference=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., articleTitle=null, refAbstract=null), Reference(id=1327011977714578065, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=33, rfOrder=36, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011977823629970, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=34, rfOrder=37, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011977882350227, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=35, rfOrder=38, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011977945264788, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=36, rfOrder=39, authorNames=null, journalName=null, refType=null, unstructuredReference=Garg N, Vazirani V V, Yannakakis M. Multiway cuts in node weighted graphs[J]. Journal of Algorithms, 2004, 50(1): 49−61, articleTitle=null, refAbstract=null), Reference(id=1327011978016567957, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=37, rfOrder=40, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011978096259734, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=38, rfOrder=41, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011978175951511, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=39, rfOrder=42, authorNames=null, journalName=null, refType=null, unstructuredReference=Speckenmeyer E. Untersuchungen zum feedback vertex set problem in ungerichteten graphen[D]. Paderborn: Universität Paderborn, 1983, articleTitle=null, refAbstract=null), Reference(id=1327011978247254680, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=40, rfOrder=43, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011978314363545, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=41, rfOrder=44, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011978373083802, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=42, rfOrder=45, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011978427609755, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=43, rfOrder=46, authorNames=null, journalName=null, refType=null, unstructuredReference=Lucchesi C L, Younger D H. A minimax theorem for directed graphs[J]. Journal of the London Mathematical Society, 1978, 2(3): 369−374, articleTitle=null, refAbstract=null), Reference(id=1327011978498912924, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=44, rfOrder=47, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011978553438877, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=45, rfOrder=48, authorNames=null, journalName=null, refType=null, unstructuredReference=Cavallaro von D. Hamiltonicity and the computational complexity of graph problems[D]. Berlin: Technische Universität Berlin, 2019, articleTitle=null, refAbstract=null), Reference(id=1327011978628936350, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=46, rfOrder=49, authorNames=null, journalName=null, refType=null, unstructuredReference=Appel K, Haken W. Every planar map is four colorable. Part I: Discharging[J]. Illinois Journal of Mathematics, 1977, 21(3): 429−490, articleTitle=null, refAbstract=null), Reference(id=1327011978708628127, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=47, rfOrder=50, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011978771542688, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=48, rfOrder=51, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011978842845857, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=49, rfOrder=52, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011978922537634, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=50, rfOrder=53, authorNames=null, journalName=null, refType=null, unstructuredReference=Cai Maocheng, Deng Xiaotie, Zang Wenan. A min-max theorem on feedback vertex sets[J]. Mathematics of Operations Research, 2002, 27(2): 361−371, articleTitle=null, refAbstract=null), Reference(id=1327011978985452195, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=51, rfOrder=54, authorNames=null, journalName=null, refType=null, unstructuredReference=Alon N. Ranking tournaments[J]. SIAM Journal on Discrete Mathematics, 2006, 20(1): 137−142, articleTitle=null, refAbstract=null), Reference(id=1327011979048366756, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=52, rfOrder=55, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011979107087013, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=53, rfOrder=56, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011979178390182, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=54, rfOrder=57, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011979241304743, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=55, rfOrder=58, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011979312607912, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=56, rfOrder=59, authorNames=null, journalName=null, refType=null, unstructuredReference=Brandstädt A, Kratsch D. On domination problems for permutation and other graphs[J]. Theoretical Computer Science, 1987, 54(2/3): 181−198, articleTitle=null, refAbstract=null), Reference(id=1327011979371328169, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=57, rfOrder=60, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011979451019946, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=58, rfOrder=61, authorNames=null, journalName=null, refType=null, unstructuredReference=Liang Y D. On the feedback vertex set problem in permutation graphs[J]. Information Processing Letters, 1994, 52(3): 123−129, articleTitle=null, refAbstract=null), Reference(id=1327011979526517419, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=59, rfOrder=62, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011979589431980, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=60, rfOrder=63, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011979643957933, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=61, rfOrder=64, authorNames=null, journalName=null, refType=null, unstructuredReference=Coorg S R, Rangan C P. Feedback vertex set on cocomparability graphs[J]. Networks, 1995, 26(2): 101−111, articleTitle=null, refAbstract=null), Reference(id=1327011979723649710, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=62, rfOrder=65, authorNames=null, journalName=null, refType=null, unstructuredReference=Liang Y D, Chang Mawshang. Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs[J]. Acta Informatica, 1997, 34(5): 337−346, articleTitle=null, refAbstract=null), Reference(id=1327011979794952879, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=63, rfOrder=66, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011979857867440, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=64, rfOrder=67, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011979916587697, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=65, rfOrder=68, authorNames=null, journalName=null, refType=null, unstructuredReference=Yannakakis M, Gavril F. The maximum
k-colorable subgraph problem for chordal graphs[J]. Information Processing Letters, 1987, 24(2): 133−137, articleTitle=null, refAbstract=null), Reference(id=1327011980034028210, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=66, rfOrder=69, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011980126302899, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=67, rfOrder=70, authorNames=null, journalName=null, refType=null, unstructuredReference=Fomin F V, Heggernes P, Kratsch D, et al. Enumerating minimal subset feedback vertex sets[J]. Algorithmica, 2014, 69(1): 216−231, articleTitle=null, refAbstract=null), Reference(id=1327011980197606068, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=68, rfOrder=71, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011980289880757, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=69, rfOrder=72, authorNames=null, journalName=null, refType=null, unstructuredReference=Marathe M V, Ravi R, Rangan C P. Generalized vertex covering in interval graphs[J]. Discrete Applied Mathematics, 1992, 39(1): 87−93, articleTitle=null, refAbstract=null), Reference(id=1327011980348601014, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=70, rfOrder=73, authorNames=null, journalName=null, refType=null, unstructuredReference=Kratsch D, Muller H, Todinca I. Feedback vertex set on AT-free graphs[J]. Discrete Applied Mathematics, 2008, 156(10): 1936−1947, articleTitle=null, refAbstract=null), Reference(id=1327011980424098487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=71, rfOrder=74, authorNames=null, journalName=null, refType=null, unstructuredReference=Poljak S. A note on stable sets and colorings of graphs[J]. Commentationes Mathematicae Niversitatis Carolinae, 1974, 15(2): 307−309, articleTitle=null, refAbstract=null), Reference(id=1327011980491207352, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=72, rfOrder=75, authorNames=null, journalName=null, refType=null, unstructuredReference=Munaro A. On line graphs of subcubic triangle-free graphs[J]. Discrete Mathematics, 2017, 340(6): 1210−1226, articleTitle=null, refAbstract=null), Reference(id=1327011980575093433, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=73, rfOrder=76, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011980654785211, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=74, rfOrder=77, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011980717699772, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=75, rfOrder=78, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011980776420029, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=76, rfOrder=79, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011980843528894, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=77, rfOrder=80, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011980898054847, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=78, rfOrder=81, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011980952580800, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=79, rfOrder=82, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1327011982206677697, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=80, rfOrder=83, authorNames=null, journalName=null, refType=null, unstructuredReference=Kloks T, Liu Chinghao, Poon Sheunghung. Feedback vertex set on chordal bipartite graphs[J]. arXiv preprint, arXiv: 1104.3915, 2011, articleTitle=null, refAbstract=null), Reference(id=1327011982676439747, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=81, rfOrder=84, authorNames=null, journalName=null, refType=null, unstructuredReference=Jiang Wei, Liu Tian, Wang Chaoyi, et al. Feedback vertex sets on restricted bipartite graphs[J]. Theoretical Computer Science, 2013, 507: 41−51, articleTitle=null, refAbstract=null), Reference(id=1327011982764520132, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=82, rfOrder=85, authorNames=null, journalName=null, refType=null, unstructuredReference=Liu Tian, Lu Min, Lu Zhao, et al. Circular convex bipartite graphs: Feedback vertex sets[J]. Theoretical Computer Science, 2014, 556: 55−62, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1327011965521736253, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, xref=null, ext=[AuthorCompanyExt(id=1327011965530124862, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, companyId=1327011965521736253, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731), AuthorCompanyExt(id=1327011965538513471, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, companyId=1327011965521736253, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=电子科技大学计算机科学与工程学院 成都 611731)])], figs=[ArticleFig(id=1327011967098794580, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Figure 1, caption=
Reductions among feedback set and subset feedback set problems in undirected graphs, figureFileSmall=F6Xa+YNMW7EqkfXkPQg2CQ==, figureFileBig=VTNPYsw9OvQvCVPD1LCGuA==, tableContent=null), ArticleFig(id=1327011968893956693, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=图1, caption=
无向图上反馈集和子集反馈集问题的归约关系, figureFileSmall=F6Xa+YNMW7EqkfXkPQg2CQ==, figureFileBig=VTNPYsw9OvQvCVPD1LCGuA==, tableContent=null), ArticleFig(id=1327011969003008598, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Figure 2, caption=
Reductions among feedback set and subset feedback set problems in directed graphs, figureFileSmall=lGNjaq5a/UqtR8OPK55+bg==, figureFileBig=XjawkKbwKohCgtn2hI/Aew==, tableContent=null), ArticleFig(id=1327011969074311767, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=图2, caption=
有向图上反馈集与子集反馈集问题的归约关系, figureFileSmall=lGNjaq5a/UqtR8OPK55+bg==, figureFileBig=XjawkKbwKohCgtn2hI/Aew==, tableContent=null), ArticleFig(id=1327011969174975064, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Figure 3, caption=
Illustrations of the polynomial-time reduction from node multiway cut to R-DSFVS, figureFileSmall=wAmq1MquJi6wX1dDPGPSmQ==, figureFileBig=uuoQk6z6cqIequW9Hg2PIA==, tableContent=null), ArticleFig(id=1327011969342747225, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=图3, caption=
节点多路割到R-DSFVS的多项式时间归约示意图, figureFileSmall=wAmq1MquJi6wX1dDPGPSmQ==, figureFileBig=uuoQk6z6cqIequW9Hg2PIA==, tableContent=null), ArticleFig(id=1327011969393078874, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Table 1, caption=
Variants of Feedback Set Problems, figureFileSmall=null, figureFileBig=null, tableContent=
| 图类型 | 反馈集 | 问题简称 |
|---|
| 无向图 | 点集 | FVS |
| 无向图 | 边集 | FES |
| 有向图 | 点集 | DFVS |
| 有向图 | 边集 | DFAS |
), ArticleFig(id=1327011969468576347, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=表1, caption=
反馈集问题类别
, figureFileSmall=null, figureFileBig=null, tableContent=
| 图类型 | 反馈集 | 问题简称 |
|---|
| 无向图 | 点集 | FVS |
| 无向图 | 边集 | FES |
| 有向图 | 点集 | DFVS |
| 有向图 | 边集 | DFAS |
), ArticleFig(id=1327011969531490908, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Table 2, caption=
Variants of Subset Feedback Set Problems, figureFileSmall=null, figureFileBig=null, tableContent=
| 图类型 | 关键集 | 反馈集 | 限制与否 | 问题简称 |
|---|
| 无向图 | 点集 | 点集 | 非限制版 | SFVS |
| 点集 | 点集 | 限制版 | R-SFVS |
| 点集 | 边集 | 非限制版 | SFES |
| 点集 | 边集 | 限制版 | |
| 边集 | 点集 | 非限制版 | ESFVS |
| 边集 | 点集 | 限制版 | |
| 边集 | 边集 | 非限制版 | ESFES |
| 边集 | 边集 | 限制版 | R-ESFES |
| 有向图 | 点集 | 点集 | 非限制版 | DSFVS |
| 点集 | 点集 | 限制版 | R-DSFVS |
| 点集 | 边集 | 非限制版 | DSFAS |
| 点集 | 边集 | 限制版 | |
| 边集 | 点集 | 非限制版 | DASFVS |
| 边集 | 点集 | 限制版 | |
| 边集 | 边集 | 非限制版 | DASFAS |
| 边集 | 边集 | 限制版 | R-DASFAS |
), ArticleFig(id=1327011969598599773, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=表2, caption=
子集反馈集问题类别
, figureFileSmall=null, figureFileBig=null, tableContent=
| 图类型 | 关键集 | 反馈集 | 限制与否 | 问题简称 |
|---|
| 无向图 | 点集 | 点集 | 非限制版 | SFVS |
| 点集 | 点集 | 限制版 | R-SFVS |
| 点集 | 边集 | 非限制版 | SFES |
| 点集 | 边集 | 限制版 | |
| 边集 | 点集 | 非限制版 | ESFVS |
| 边集 | 点集 | 限制版 | |
| 边集 | 边集 | 非限制版 | ESFES |
| 边集 | 边集 | 限制版 | R-ESFES |
| 有向图 | 点集 | 点集 | 非限制版 | DSFVS |
| 点集 | 点集 | 限制版 | R-DSFVS |
| 点集 | 边集 | 非限制版 | DSFAS |
| 点集 | 边集 | 限制版 | |
| 边集 | 点集 | 非限制版 | DASFVS |
| 边集 | 点集 | 限制版 | |
| 边集 | 边集 | 非限制版 | DASFAS |
| 边集 | 边集 | 限制版 | R-DASFAS |
), ArticleFig(id=1327011969690874462, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Table 3, caption=
Complexity of Subset Feedback Set Problem When $ \mathit{l} $ is a Constant, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | $ l$的值 | 计算复杂性 |
|---|
| R-SFVS | 固定的$ l\ge 1 $ | NP难[18] |
| R-SEFES | $ l=1 $ | $ \mathrm{P} $[19] |
| 固定的$ l\ge 2 $ | NP难 [19] |
| R-DSFVS | $ l=1 $ | $ \mathrm{P} $[17] |
| 固定的$ l\ge 2 $ | NP难 [17] |
| R-DASFAS | $ l=1 $ | $ \mathrm{P} $[17] |
| 固定的$ l\ge 2 $ | NP难[17] |
), ArticleFig(id=1327011969749594719, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=表3, caption=
子集反馈集问题在$ \mathit{l} $为常数时的计算复杂性
, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | $ l$的值 | 计算复杂性 |
|---|
| R-SFVS | 固定的$ l\ge 1 $ | NP难[18] |
| R-SEFES | $ l=1 $ | $ \mathrm{P} $[19] |
| 固定的$ l\ge 2 $ | NP难 [19] |
| R-DSFVS | $ l=1 $ | $ \mathrm{P} $[17] |
| 固定的$ l\ge 2 $ | NP难 [17] |
| R-DASFAS | $ l=1 $ | $ \mathrm{P} $[17] |
| 固定的$ l\ge 2 $ | NP难[17] |
), ArticleFig(id=1327011969833480800, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Table 4, caption=
Complexity of Feedback Set Problems in Degree Bounded Graphs, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS | 3度图 | O(n2log6n)[40-41] |
| FVS | 4度图 | NP难[39] |
| DFVS | 最大出度为1的有向图 | $ O\left(n\right) $ |
| DFAS | 最大出度为1的有向图 | $ O\left(n\right) $ |
| DFVS | 最大出入度为2的有向图 | NP难[38] |
| DFAS | 最大出入度为3的有向图 | NP难[38] |
), ArticleFig(id=1327011969896395361, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=表4, caption=
度有界的图上的反馈集问题的计算复杂性
, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS | 3度图 | O(n2log6n)[40-41] |
| FVS | 4度图 | NP难[39] |
| DFVS | 最大出度为1的有向图 | $ O\left(n\right) $ |
| DFAS | 最大出度为1的有向图 | $ O\left(n\right) $ |
| DFVS | 最大出入度为2的有向图 | NP难[38] |
| DFAS | 最大出入度为3的有向图 | NP难[38] |
), ArticleFig(id=1327011969967698530, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Table 5, caption=
Complexity of Feedback Set and Subset Feedback Set Problems in Planar Graphs, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS | 3度平面图 | O(n2log6n)[40-41] |
| FVS | 4正则哈密顿平面图 | NP难[45] |
| SFVS | 补平面图 | P [定理4] |
| DFVS | 最大出入度为3的平面有向图 | NP难[38] |
| DFAS | 平面图 | O(n2.5logn)[43-44] |
), ArticleFig(id=1327011970026418787, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=表5, caption=
平面图上的反馈集和子集反馈集问题的计算复杂性
, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS | 3度平面图 | O(n2log6n)[40-41] |
| FVS | 4正则哈密顿平面图 | NP难[45] |
| SFVS | 补平面图 | P [定理4] |
| DFVS | 最大出入度为3的平面有向图 | NP难[38] |
| DFAS | 平面图 | O(n2.5logn)[43-44] |
), ArticleFig(id=1327011970122887780, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Table 6, caption=
Complexity of Feedback Set and Subset Feedback Set Problems in Tournaments and Bipartite Tournaments, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| DFVS | 竞赛图 | NP难[49] |
| DFAS | 竞赛图 | NP难[51-53] |
| DFVS | 二部竞赛图 | NP难[51] |
| DFAS | 二部竞赛图 | NP难[54] |
), ArticleFig(id=1327011970177413733, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=表6, caption=
竞赛图和二部竞赛图上的反馈集和子集反馈集问题的计算复杂性
, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| DFVS | 竞赛图 | NP难[49] |
| DFAS | 竞赛图 | NP难[51-53] |
| DFVS | 二部竞赛图 | NP难[51] |
| DFAS | 二部竞赛图 | NP难[54] |
), ArticleFig(id=1327011970240328294, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Table 7, caption=
Complexity of Feedback Set and Subset Feedback Set Problems in Intersection Graphs, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS | 置换图 | O(nm)[58] |
| SFVS | 置换图 | O(m3)[64] |
| FVS | 补比较图 | O(n2m)[62] |
| FVS | 圆图 | O(n7)[63] |
| FVS | 圆-d-拱形图 | O(n2d+5)[63] |
| SFVS | 弧线图 | O(n4)[64] |
| FVS | 弦图 | O(n4)[65] |
| FVS | 分裂图 | O(n2)[65] |
| SFVS | 弦图/分裂图 | NP难[67] |
| R-SFVS | 弦图/分裂图 | NP难[67] |
| FVS | 区间图 | O(m)[66] |
| SFVS | 区间图 | O(n3)[64] |
| R-SFVS | 区间图 | O(n3)[68-69] |
), ArticleFig(id=1327011970357768807, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=表7, caption=
相交图上的反馈集和子集反馈集问题的计算复杂性
, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS | 置换图 | O(nm)[58] |
| SFVS | 置换图 | O(m3)[64] |
| FVS | 补比较图 | O(n2m)[62] |
| FVS | 圆图 | O(n7)[63] |
| FVS | 圆-d-拱形图 | O(n2d+5)[63] |
| SFVS | 弧线图 | O(n4)[64] |
| FVS | 弦图 | O(n4)[65] |
| FVS | 分裂图 | O(n2)[65] |
| SFVS | 弦图/分裂图 | NP难[67] |
| R-SFVS | 弦图/分裂图 | NP难[67] |
| FVS | 区间图 | O(m)[66] |
| SFVS | 区间图 | O(n3)[64] |
| R-SFVS | 区间图 | O(n3)[68-69] |
), ArticleFig(id=1327011970424877672, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Table 8, caption=
Complexity of Feedback Set and Subset Feedback Set Problems in Forbidden Graphs, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS | AT-free | O(n8m2)[70] |
| FVS | $ H $-free ($ {C}_{r}\subseteq H,r\ge 3) $ | NP难[71] |
| FVS | 线图 | NP难[72] |
| FVS | $ (s{P}_{1}+{P}_{5}) $-free ($ s\ge 0 $) | P[73-76] |
| FVS | $ s{P}_{3} $-free ($ s\ge 1) $ | P[74,76] |
| SFVS | $ (2{P}_{1}+{P}_{4}) $-free | P[77] |
| SFVS | $ H $-free $ (H\nsubseteq 2{P}_{1}+{P}_{4} $) | NP难[77] |
), ArticleFig(id=1327011970491986537, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=表8, caption=
禁止图图类上反馈集和子集反馈集问题的计算复杂性
, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS | AT-free | O(n8m2)[70] |
| FVS | $ H $-free ($ {C}_{r}\subseteq H,r\ge 3) $ | NP难[71] |
| FVS | 线图 | NP难[72] |
| FVS | $ (s{P}_{1}+{P}_{5}) $-free ($ s\ge 0 $) | P[73-76] |
| FVS | $ s{P}_{3} $-free ($ s\ge 1) $ | P[74,76] |
| SFVS | $ (2{P}_{1}+{P}_{4}) $-free | P[77] |
| SFVS | $ H $-free $ (H\nsubseteq 2{P}_{1}+{P}_{4} $) | NP难[77] |
), ArticleFig(id=1327011970634592874, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=EN, label=Table 9, caption=
Complexity of Feedback Set and Subset Feedback Set Problems in Bipartite Graph Classes, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS/DFVS | 二部图 | NP难 |
| FVS | 路凸二部图 | $ O\left({n}^{2}m\right) $[62] |
| FVS | 3度树凸二部图 | NP难[81] |
| FVS | 星凸二部图 | NP难[79] |
| FVS | 弦凸二部图 | $ O\left({n}^{5}\right) $[80] |
| FVS | 环凸二部图 | $ O\left({n}^{4}m\right) $[82] |
| SFVS | 补二部图 | $ O\left({n}^{4}\right) $[64] |
), ArticleFig(id=1327011970697507435, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011514155905155, language=CN, label=表9, caption=
二部图图类上反馈集和子集反馈集问题的计算复杂性
, figureFileSmall=null, figureFileBig=null, tableContent=
| 问题 | 图类 | 计算复杂性 |
|---|
| FVS/DFVS | 二部图 | NP难 |
| FVS | 路凸二部图 | $ O\left({n}^{2}m\right) $[62] |
| FVS | 3度树凸二部图 | NP难[81] |
| FVS | 星凸二部图 | NP难[79] |
| FVS | 弦凸二部图 | $ O\left({n}^{5}\right) $[80] |
| FVS | 环凸二部图 | $ O\left({n}^{4}m\right) $[82] |
| SFVS | 补二部图 | $ O\left({n}^{4}\right) $[64] |
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202330693, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330693, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202330693, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202330693, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1735660800000, fullTextJson=null, articleText=null, reference=null)