627:
of an operating system, each directed cycle corresponds to a deadlock situation. In order to resolve all deadlocks, some blocked processes have to be aborted. A minimum feedback vertex set in this graph corresponds to a minimum number of processes that one needs to
402:
is the number of vertices in the graph. This algorithm actually computes a maximum induced forest, and when such a forest is obtained, its complement is a minimum feedback vertex set. The number of minimal feedback vertex sets in a graph is bounded by
638:
Another application is in complexity theory. Some computational problems on graphs are NP-hard in general, but can be solved in polynomial time for graphs with bounded FVS number. Some examples are graph isomorphism and the path reconfiguration
1530:
487:
problem, but since the feedback arc set problem and feedback vertex set problem in directed graphs are reducible to one another while preserving solution sizes, it also holds for the latter.
1464:
Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three",
367:. The problem remains NP-complete on directed graphs with maximum in-degree and out-degree two, and on directed planar graphs with maximum in-degree and out-degree three.
168:
578:
204:
119:
483:, it is NP-hard to approximate the problem to within any constant factor in polynomial time. The same hardness result was originally proven for the closely related
1088:
Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.",
327:
307:
287:
244:
224:
139:
1194:
Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem",
341:). Thus, finding a minimum FVS in a graph is equivalent to finding a maximum induced forest (resp. maximum induced directed acyclic graph in the case of
1330:
Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "On the minimum feedback vertex set problem: exact and enumeration algorithms.",
36:("removal" means deleting the vertex and all edges adjacent to it). Equivalently, each FVS contains at least one vertex of any cycle in the graph. The
512:- a set of edges in an undirected graph, whose removal makes the graph acyclic. The size of a smallest feedback edge set in a graph is called the
1585:
499:, the size of a minimum feedback vertex set is within a logarithmic factor of the maximum number of vertex-disjoint cycles in the given graph.
1164:
Chen, Jianer; Fomin, Fedor V.; Liu, Yang; Lu, Songjian; Villanger, Yngve (2008), "Improved algorithms for feedback vertex set problems",
1042:
1011:
Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro (1999), "A 2-approximation algorithm for the undirected feedback vertex set problem",
415:
is the number of vertices in the given directed graph. The parameterized versions of the directed and undirected problems are both
1418:
Li, Deming; Liu, Yanpei (1999), "A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph",
1166:
1236:
1562:
1544:
1155:
1120:
Cao, Yixin; Chen, Jianer; Liu, Yang (2010), "On feedback vertex set: new measure and new structures", in Kaplan, Haim (ed.),
978:
941:
805:
1389:
1090:
480:
49:
605:(FAS) - a set of directed arcs whose removal makes the graph acyclic. Finding a smallest FAS is an NP-hard problem.
1302:
1122:
Proc. 12th
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Norway, June 21-23, 2010
1411:
Proc. Symposium on
Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.
1466:
957:
1580:
1290:
81:
29:
1040:
Becker, Ann; Bar-Yehuda, Reuven; Geiger, Dan (2000), "Randomized algorithms for the loop cutset problem",
620:
496:
475:
By contrast, the directed version of the problem appears to be much harder to approximate. Under the
416:
1346:
1104:
920:. Lecture Notes in Computer Science. Vol. 6139. Berlin, Heidelberg: Springer. pp. 81–92.
581:
1370:
Fomin, Fedor V.; Villanger, Yngve (2010), "Finding induced subgraphs via minimal triangulations",
147:
521:
476:
391:
1451:
913:
1341:
1099:
431:
334:
173:
1536:
1244:
584:
of the graph. The problem of finding a smallest feedback edge set is equivalent to finding a
423:
379:
375:
330:
86:
1374:, Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, pp. 383–394,
518:
of the graph. In contrast to the FVS number, the circuit rank can be easily computed: it is
1489:
1447:
1439:
1265:
1217:
1187:
1135:
1073:
1032:
921:
247:
33:
1372:
Proc. 27th
International Symposium on Theoretical Aspects of Computer Science (STACS 2010)
8:
1139:
925:
1395:
1359:
1319:
1221:
1196:
1125:
1077:
1051:
984:
858:
811:
312:
292:
257:
229:
209:
124:
1446:
Razgon, I. (2007), "Computing minimum directed feedback vertex set in O*(1.9977)", in
1431:
1558:
1540:
1480:
1385:
1323:
1151:
1113:
988:
974:
937:
850:
801:
1081:
786:"Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph"
1526:
1522:
1505:
1475:
1427:
1380:
1375:
1351:
1311:
1269:
1253:
1225:
1205:
1175:
1143:
1109:
1061:
1020:
966:
929:
862:
842:
815:
793:
616:
601:
484:
472:
The best known approximation algorithm on undirected graphs is by a factor of two.
73:
53:
1399:
1363:
1509:
1485:
1435:
1261:
1213:
1183:
1147:
1069:
1028:
589:
427:
57:
1257:
933:
1179:
785:
624:
596:
435:
407:(1.8638). The directed feedback vertex set problem can still be solved in time
357:
342:
338:
1355:
1024:
970:
830:
1574:
854:
774:
for an alternative approximation algorithm with the same approximation ratio.
585:
1286:
1209:
394:
of finding the size of a minimum feedback vertex set can be solved in time
1406:
1332:
1315:
1294:
514:
455:
21:
1453:
Proceedings of the 10th
Italian Conference on Theoretical Computer Science
797:
462:
364:
45:
17:
784:
Guruswami, Venkatesan; Manokaran, Rajsekar; Raghavendra, Prasad (2008).
370:
Karp's reduction also implies the NP-completeness of the FVS problem on
1508:(2000), "Feedback set problems", in Du, D.-Z.; Pardalos, P. M. (eds.),
1232:
846:
1532:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
1124:, Lecture Notes in Computer Science, vol. 6139, pp. 93–104,
831:"Approximating Minimum Feedback Sets and Multicuts in Directed Graphs"
1065:
688:
378:
four. The FVS problem can be solved in polynomial time on graphs of
881:
1130:
1056:
790:
2008 49th Annual IEEE Symposium on
Foundations of Computer Science
712:
893:
1553:
Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008),
914:"Isomorphism for Graphs of Bounded Feedback Vertex Set Number"
40:
of a graph is the size of a smallest feedback vertex set. The
828:
783:
619:, feedback vertex sets play a prominent role in the study of
965:. Lecture Notes in Computer Science. Vol. 11646. 2019.
829:
Even, G.; (Seffi) Naor, J.; Schieber, B.; Sudan, M. (1998).
724:
632:
61:
32:
is a set of vertices whose removal leaves a graph without
1511:
1329:
694:
447:
426:
three, the feedback vertex set problem can be solved in
1552:
1237:"On the hardness of approximating minimum vertex cover"
1193:
887:
718:
1039:
1409:(1972), "Reducibility Among Combinatorial Problems",
869:
524:
374:
graphs, where the problem stays NP-hard on graphs of
315:
295:
260:
232:
212:
176:
150:
127:
89:
1503:
899:
631:
The feedback vertex set problem has applications in
655:unpublished results due to Garey and Johnson, cf.
572:
468:Existing constant-factor approximation algorithms.
321:
301:
281:
238:
218:
198:
162:
133:
113:
1463:
1010:
911:
771:
730:
700:
668:
1572:
1497:
1517:, Kluwer Academic Publishers, pp. 209–259
1369:
1295:"On independent circuits contained in a graph"
1163:
683:
461:The existence of an approximation preserving
430:, by transforming it into an instance of the
1557:(8th ed.), John Wiley & Sons. Inc,
1521:
1087:
912:Kratsch, Stefan; Schweitzer, Pascal (2010).
767:
656:
1043:Journal of Artificial Intelligence Research
1231:
1119:
742:
226:and their adjacent edges are deleted from
1479:
1379:
1345:
1285:
1129:
1103:
1055:
875:
450:. This follows from the following facts.
508:Instead of vertices, one can consider a
356:showed that the minimum FVS problem for
1450:; Moggi, Eugenio; Laura, Luigi (eds.),
1167:Journal of Computer and System Sciences
888:Silberschatz, Galvin & Gagne (2008)
1586:Computational problems in graph theory
1573:
1445:
706:
80:INSTANCE: An (undirected or directed)
50:first problems shown to be NP-complete
1417:
752:
750:
672:
1405:
1013:SIAM Journal on Discrete Mathematics
1003:
900:Festa, Pardalos & Resende (2000)
756:
465:from the vertex cover problem to it;
353:
1413:, New York: Plenum, pp. 85–103
502:
385:
42:minimum feedback vertex set problem
13:
1459:, World Scientific, pp. 70–81
747:
14:
1597:
772:Bafna, Berman & Fujito (1999)
731:Ueno, Kajitani & Gotoh (1988)
669:Ueno, Kajitani & Gotoh (1988)
481:computational hardness assumption
270:
479:, an unproven but commonly used
441:
422:In undirected graphs of maximum
206:such that, when all vertices of
1303:Canadian Journal of Mathematics
950:
905:
822:
777:
761:
609:
1381:10.4230/LIPIcs.STACS.2010.2470
959:Algorithms and Data Structures
736:
677:
662:
649:
566:
558:
550:
542:
534:
526:
348:
276:
264:
186:
178:
108:
96:
52:. It has wide applications in
1:
1498:Textbooks and survey articles
1432:10.1016/s0252-9602(17)30520-9
998:
67:
1504:Festa, P.; Pardalos, P. M.;
1481:10.1016/0012-365X(88)90226-9
1148:10.1007/978-3-642-13731-0_10
1114:10.1016/0004-3702(95)00004-6
918:Algorithm Theory - SWAT 2010
684:Fomin & Villanger (2010)
454:The APX-completeness of the
289:that remains after removing
163:{\displaystyle X\subseteq V}
144:QUESTION: Is there a subset
7:
1258:10.4007/annals.2005.162.439
1019:(3): 289–297 (electronic),
934:10.1007/978-3-642-13731-0_9
595:The analogous concept in a
573:{\displaystyle |E|-|V|+|C|}
10:
1602:
1180:10.1016/j.jcss.2008.05.002
768:Becker & Geiger (1996)
657:Garey & Johnson (1979)
446:The undirected problem is
48:problem; it was among the
38:feedback vertex set number
1555:Operating System Concepts
1420:Acta Mathematica Scientia
1356:10.1007/s00453-007-9152-0
1025:10.1137/S0895480196305124
971:10.1007/978-3-030-24766-9
916:. In Kaplan, Haim (ed.).
490:
417:fixed-parameter tractable
199:{\displaystyle |X|\leq k}
1235:; Safra, Samuel (2005),
643:
580:, where C is the set of
1210:10.1145/1411509.1411511
1091:Artificial Intelligence
876:Erdős & Pósa (1965)
588:, which can be done in
477:unique games conjecture
392:NP optimization problem
121:and a positive integer
114:{\displaystyle G=(V,E)}
1537:A1.1: GT7, p. 191
1316:10.4153/CJM-1965-035-8
743:Dinur & Safra 2005
574:
432:matroid parity problem
335:directed acyclic graph
323:
303:
283:
240:
220:
200:
164:
135:
115:
1448:Italiano, Giuseppe F.
1245:Annals of Mathematics
575:
324:
304:
284:
241:
221:
201:
165:
136:
116:
1581:NP-complete problems
1467:Discrete Mathematics
798:10.1109/FOCS.2008.51
792:. pp. 573–582.
582:connected components
522:
456:vertex cover problem
313:
293:
258:
230:
210:
174:
148:
125:
87:
1140:2010LNCS.6139...93C
926:2010LNCS.6139...81K
695:Fomin et al. (2008)
673:Li & Liu (1999)
246:, the remainder is
26:feedback vertex set
1197:Journal of the ACM
847:10.1007/PL00009191
719:Chen et al. (2008)
570:
497:Erdős–Pósa theorem
390:The corresponding
333:(resp. an induced
319:
299:
279:
236:
216:
196:
160:
131:
111:
1564:978-0-470-12872-5
1546:978-0-7167-1045-5
1527:Johnson, David S.
1523:Garey, Michael R.
1248:, Second Series,
1157:978-3-642-13730-3
1004:Research articles
980:978-3-030-24765-2
943:978-3-642-13731-0
807:978-0-7695-3436-7
623:recovery. In the
617:operating systems
510:feedback edge set
495:According to the
398:(1.7347), where
322:{\displaystyle G}
302:{\displaystyle X}
282:{\displaystyle G}
239:{\displaystyle G}
219:{\displaystyle X}
134:{\displaystyle k}
54:operating systems
1593:
1567:
1549:
1535:, W.H. Freeman,
1518:
1516:
1492:
1483:
1474:(1–3): 355–360,
1460:
1458:
1442:
1414:
1407:Karp, Richard M.
1402:
1383:
1366:
1349:
1326:
1299:
1282:
1281:
1280:
1274:
1268:, archived from
1241:
1228:
1190:
1174:(7): 1188–1198,
1160:
1133:
1116:
1107:
1084:
1066:10.1613/jair.638
1059:
1035:
993:
992:
964:
954:
948:
947:
909:
903:
897:
891:
885:
879:
873:
867:
866:
826:
820:
819:
781:
775:
765:
759:
754:
745:
740:
734:
728:
722:
716:
710:
704:
698:
692:
686:
681:
675:
666:
660:
653:
602:feedback arc set
579:
577:
576:
571:
569:
561:
553:
545:
537:
529:
503:Related concepts
485:feedback arc set
411:(1.9977), where
386:Exact algorithms
328:
326:
325:
320:
308:
306:
305:
300:
288:
286:
285:
280:
245:
243:
242:
237:
225:
223:
222:
217:
205:
203:
202:
197:
189:
181:
169:
167:
166:
161:
140:
138:
137:
132:
120:
118:
117:
112:
74:decision problem
58:database systems
1601:
1600:
1596:
1595:
1594:
1592:
1591:
1590:
1571:
1570:
1565:
1547:
1514:
1506:Resende, M.G.C.
1500:
1495:
1456:
1392:
1347:10.1.1.722.8913
1297:
1278:
1276:
1272:
1239:
1158:
1006:
1001:
996:
981:
962:
956:
955:
951:
944:
910:
906:
898:
894:
886:
882:
874:
870:
827:
823:
808:
782:
778:
766:
762:
755:
748:
741:
737:
729:
725:
717:
713:
705:
701:
693:
689:
682:
678:
667:
663:
654:
650:
646:
612:
590:polynomial time
586:spanning forest
565:
557:
549:
541:
533:
525:
523:
520:
519:
505:
493:
444:
436:linear matroids
428:polynomial time
388:
382:at most three.
351:
343:directed graphs
339:directed graphs
337:in the case of
314:
311:
310:
294:
291:
290:
259:
256:
255:
231:
228:
227:
211:
208:
207:
185:
177:
175:
172:
171:
149:
146:
145:
126:
123:
122:
88:
85:
84:
76:is as follows:
70:
12:
11:
5:
1599:
1589:
1588:
1583:
1569:
1568:
1563:
1550:
1545:
1519:
1499:
1496:
1494:
1493:
1461:
1443:
1426:(4): 375–381,
1415:
1403:
1390:
1367:
1340:(2): 293–307,
1327:
1283:
1252:(1): 439–485,
1229:
1204:(5), Art. 21,
1191:
1161:
1156:
1117:
1105:10.1.1.25.1442
1098:(1): 167–188,
1085:
1037:
1007:
1005:
1002:
1000:
997:
995:
994:
979:
949:
942:
904:
892:
880:
868:
841:(2): 151–174.
821:
806:
776:
760:
746:
735:
723:
711:
699:
687:
676:
661:
647:
645:
642:
641:
640:
636:
629:
625:wait-for graph
611:
608:
607:
606:
597:directed graph
593:
568:
564:
560:
556:
552:
548:
544:
540:
536:
532:
528:
504:
501:
492:
489:
470:
469:
466:
459:
443:
440:
387:
384:
380:maximum degree
376:maximum degree
350:
347:
329:is an induced
318:
298:
278:
275:
272:
269:
266:
263:
252:
251:
235:
215:
195:
192:
188:
184:
180:
159:
156:
153:
142:
130:
110:
107:
104:
101:
98:
95:
92:
69:
66:
20:discipline of
9:
6:
4:
3:
2:
1598:
1587:
1584:
1582:
1579:
1578:
1576:
1566:
1560:
1556:
1551:
1548:
1542:
1538:
1534:
1533:
1528:
1524:
1520:
1513:
1512:
1507:
1502:
1501:
1491:
1487:
1482:
1477:
1473:
1469:
1468:
1462:
1455:
1454:
1449:
1444:
1441:
1437:
1433:
1429:
1425:
1421:
1416:
1412:
1408:
1404:
1401:
1397:
1393:
1391:9783939897163
1387:
1382:
1377:
1373:
1368:
1365:
1361:
1357:
1353:
1348:
1343:
1339:
1335:
1334:
1328:
1325:
1321:
1317:
1313:
1309:
1305:
1304:
1296:
1292:
1288:
1284:
1275:on 2009-09-20
1271:
1267:
1263:
1259:
1255:
1251:
1247:
1246:
1238:
1234:
1230:
1227:
1223:
1219:
1215:
1211:
1207:
1203:
1199:
1198:
1192:
1189:
1185:
1181:
1177:
1173:
1169:
1168:
1162:
1159:
1153:
1149:
1145:
1141:
1137:
1132:
1127:
1123:
1118:
1115:
1111:
1106:
1101:
1097:
1093:
1092:
1086:
1083:
1079:
1075:
1071:
1067:
1063:
1058:
1053:
1049:
1045:
1044:
1038:
1034:
1030:
1026:
1022:
1018:
1014:
1009:
1008:
990:
986:
982:
976:
972:
968:
961:
960:
953:
945:
939:
935:
931:
927:
923:
919:
915:
908:
901:
896:
889:
884:
877:
872:
864:
860:
856:
852:
848:
844:
840:
836:
832:
825:
817:
813:
809:
803:
799:
795:
791:
787:
780:
773:
769:
764:
758:
753:
751:
744:
739:
732:
727:
720:
715:
708:
707:Razgon (2007)
703:
696:
691:
685:
680:
674:
670:
665:
658:
652:
648:
637:
634:
630:
626:
622:
618:
614:
613:
604:
603:
598:
594:
591:
587:
583:
562:
554:
546:
538:
530:
517:
516:
511:
507:
506:
500:
498:
488:
486:
482:
478:
473:
467:
464:
460:
457:
453:
452:
451:
449:
442:Approximation
439:
437:
433:
429:
425:
420:
418:
414:
410:
406:
401:
397:
393:
383:
381:
377:
373:
368:
366:
362:
360:
355:
346:
344:
340:
336:
332:
316:
296:
273:
267:
261:
249:
233:
213:
193:
190:
182:
157:
154:
151:
143:
128:
105:
102:
99:
93:
90:
83:
79:
78:
77:
75:
65:
64:chip design.
63:
59:
55:
51:
47:
43:
39:
35:
31:
27:
23:
19:
1554:
1531:
1510:
1471:
1465:
1452:
1423:
1419:
1410:
1371:
1337:
1333:Algorithmica
1331:
1307:
1301:
1277:, retrieved
1270:the original
1249:
1243:
1201:
1195:
1171:
1165:
1121:
1095:
1089:
1047:
1041:
1016:
1012:
958:
952:
917:
907:
895:
883:
871:
838:
835:Algorithmica
834:
824:
789:
779:
763:
738:
726:
714:
702:
690:
679:
664:
651:
635:chip design.
610:Applications
600:
515:circuit rank
513:
509:
494:
474:
471:
448:APX-complete
445:
421:
412:
408:
404:
399:
395:
389:
371:
369:
358:
352:
253:
71:
41:
37:
25:
22:graph theory
18:mathematical
15:
1310:: 347–352,
1291:Pósa, Lajos
1287:Erdős, Paul
1233:Dinur, Irit
1050:: 219–234,
770:. See also
757:Karp (1972)
463:L-reduction
365:NP-complete
354:Karp (1972)
349:NP-hardness
46:NP-complete
28:(FVS) of a
1575:Categories
1279:2010-03-29
999:References
372:undirected
254:The graph
248:cycle-free
68:Definition
1342:CiteSeerX
1324:123981328
1131:1004.1672
1100:CiteSeerX
1057:1106.0225
989:198996919
855:0178-4617
539:−
271:∖
191:≤
155:⊆
1529:(1979),
1293:(1965),
1082:10243677
639:problem.
621:deadlock
359:directed
72:The FVS
1490:0975556
1440:1735603
1266:2178966
1226:1547510
1218:2456546
1188:2454063
1136:Bibcode
1074:1765590
1033:1710236
922:Bibcode
863:2437790
816:8762205
599:is the
16:In the
1561:
1543:
1488:
1438:
1400:436224
1398:
1388:
1364:731997
1362:
1344:
1322:
1264:
1224:
1216:
1186:
1154:
1102:
1080:
1072:
1031:
987:
977:
940:
861:
853:
814:
804:
628:abort.
491:Bounds
424:degree
361:graphs
331:forest
60:, and
44:is an
34:cycles
1515:(PDF)
1457:(PDF)
1396:S2CID
1360:S2CID
1320:S2CID
1298:(PDF)
1273:(PDF)
1240:(PDF)
1222:S2CID
1126:arXiv
1078:S2CID
1052:arXiv
985:S2CID
963:(PDF)
859:S2CID
812:S2CID
659:: GT7
644:Notes
309:from
170:with
82:graph
30:graph
1559:ISBN
1541:ISBN
1386:ISBN
1152:ISBN
975:ISBN
938:ISBN
851:ISSN
802:ISBN
633:VLSI
434:for
62:VLSI
24:, a
1476:doi
1428:doi
1376:doi
1352:doi
1312:doi
1254:doi
1250:162
1206:doi
1176:doi
1144:doi
1110:doi
1062:doi
1021:doi
967:doi
930:doi
843:doi
794:doi
615:In
363:is
345:).
1577::
1539:,
1525:;
1486:MR
1484:,
1472:72
1470:,
1436:MR
1434:,
1424:19
1422:,
1394:,
1384:,
1358:,
1350:,
1338:52
1336:,
1318:,
1308:17
1306:,
1300:,
1289:;
1262:MR
1260:,
1242:,
1220:,
1214:MR
1212:,
1202:55
1200:,
1184:MR
1182:,
1172:74
1170:,
1150:,
1142:,
1134:,
1108:,
1096:83
1094:,
1076:,
1070:MR
1068:,
1060:,
1048:12
1046:,
1029:MR
1027:,
1017:12
1015:,
983:.
973:.
936:.
928:.
857:.
849:.
839:20
837:.
833:.
810:.
800:.
788:.
749:^
671:;
438:.
419:.
409:O*
56:,
1478::
1430::
1378::
1354::
1314::
1256::
1208::
1178::
1146::
1138::
1128::
1112::
1064::
1054::
1036:.
1023::
991:.
969::
946:.
932::
924::
902:.
890:.
878:.
865:.
845::
818:.
796::
733:.
721:.
709:.
697:.
592:.
567:|
563:C
559:|
555:+
551:|
547:V
543:|
535:|
531:E
527:|
458:;
413:n
405:O
400:n
396:O
317:G
297:X
277:]
274:X
268:V
265:[
262:G
250:?
234:G
214:X
194:k
187:|
183:X
179:|
158:V
152:X
141:.
129:k
109:)
106:E
103:,
100:V
97:(
94:=
91:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.