Dynamic thresholding search for the feedback vertex set problem
Given a directed graph G = (V, E), a feedback vertex set is a vertex subset C whose removal makes the graph G acyclic. The feedback vertex set problem is to find the subset C* whose cardinality is the minimum. As a general model, this problem has a variety of applications. However, the problem is kn...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
PeerJ Inc.
2023-02-01
|
| Series: | PeerJ Computer Science |
| Subjects: | |
| Online Access: | https://peerj.com/articles/cs-1245.pdf |
| _version_ | 1811165602891431936 |
|---|---|
| author | Wen Sun Jin-Kao Hao Zihao Wu Wenlong Li Qinghua Wu |
| author_facet | Wen Sun Jin-Kao Hao Zihao Wu Wenlong Li Qinghua Wu |
| author_sort | Wen Sun |
| collection | DOAJ |
| description | Given a directed graph G = (V, E), a feedback vertex set is a vertex subset C whose removal makes the graph G acyclic. The feedback vertex set problem is to find the subset C* whose cardinality is the minimum. As a general model, this problem has a variety of applications. However, the problem is known to be NP-hard, and thus computationally challenging. To solve this difficult problem, this article develops an iterated dynamic thresholding search algorithm, which features a combination of local optimization, dynamic thresholding search, and perturbation. Computational experiments on 101 benchmark graphs from various sources demonstrate the advantage of the algorithm compared with the state-of-the-art algorithms, by reporting record-breaking best solutions for 24 graphs, equally best results for 75 graphs, and worse best results for only two graphs. We also study how the key components of the algorithm affect its performance of the algorithm. |
| first_indexed | 2024-04-10T15:40:20Z |
| format | Article |
| id | doaj.art-dd4634be444c41798ed133d0f244dbc5 |
| institution | Directory Open Access Journal |
| issn | 2376-5992 |
| language | English |
| last_indexed | 2024-04-10T15:40:20Z |
| publishDate | 2023-02-01 |
| publisher | PeerJ Inc. |
| record_format | Article |
| series | PeerJ Computer Science |
| spelling | doaj.art-dd4634be444c41798ed133d0f244dbc52023-02-12T15:05:13ZengPeerJ Inc.PeerJ Computer Science2376-59922023-02-019e124510.7717/peerj-cs.1245Dynamic thresholding search for the feedback vertex set problemWen Sun0Jin-Kao Hao1Zihao Wu2Wenlong Li3Qinghua Wu4School of Cyber Science and Engineering, Southeast University, Nanjing, ChinaLERIA, Université d’Angers, Angers, FranceSchool of Cyber Science and Engineering, Southeast University, Nanjing, ChinaSchool of Cyber Science and Engineering, Southeast University, Nanjing, ChinaSchool of Management, Huazhong University of Science and Technology, Wuhan, ChinaGiven a directed graph G = (V, E), a feedback vertex set is a vertex subset C whose removal makes the graph G acyclic. The feedback vertex set problem is to find the subset C* whose cardinality is the minimum. As a general model, this problem has a variety of applications. However, the problem is known to be NP-hard, and thus computationally challenging. To solve this difficult problem, this article develops an iterated dynamic thresholding search algorithm, which features a combination of local optimization, dynamic thresholding search, and perturbation. Computational experiments on 101 benchmark graphs from various sources demonstrate the advantage of the algorithm compared with the state-of-the-art algorithms, by reporting record-breaking best solutions for 24 graphs, equally best results for 75 graphs, and worse best results for only two graphs. We also study how the key components of the algorithm affect its performance of the algorithm.https://peerj.com/articles/cs-1245.pdfFeedback vertex setDynamic thresholding searchDescent searchHeuristic |
| spellingShingle | Wen Sun Jin-Kao Hao Zihao Wu Wenlong Li Qinghua Wu Dynamic thresholding search for the feedback vertex set problem PeerJ Computer Science Feedback vertex set Dynamic thresholding search Descent search Heuristic |
| title | Dynamic thresholding search for the feedback vertex set problem |
| title_full | Dynamic thresholding search for the feedback vertex set problem |
| title_fullStr | Dynamic thresholding search for the feedback vertex set problem |
| title_full_unstemmed | Dynamic thresholding search for the feedback vertex set problem |
| title_short | Dynamic thresholding search for the feedback vertex set problem |
| title_sort | dynamic thresholding search for the feedback vertex set problem |
| topic | Feedback vertex set Dynamic thresholding search Descent search Heuristic |
| url | https://peerj.com/articles/cs-1245.pdf |
| work_keys_str_mv | AT wensun dynamicthresholdingsearchforthefeedbackvertexsetproblem AT jinkaohao dynamicthresholdingsearchforthefeedbackvertexsetproblem AT zihaowu dynamicthresholdingsearchforthefeedbackvertexsetproblem AT wenlongli dynamicthresholdingsearchforthefeedbackvertexsetproblem AT qinghuawu dynamicthresholdingsearchforthefeedbackvertexsetproblem |