Feedback vertex set

<h2 id="definition">Definition</h2>
The FVS <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> is as follows:

INSTANCE: An (undirected or directed) <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> 
 
 
 
 G
 =
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G=(V,E)}
 
 and a positive integer 
 
 
 
 k
 
 
 {\displaystyle k}
 
.
QUESTION: Is there a subset 
 
 
 
 X
 ⊆
 V
 
 
 {\displaystyle X\subseteq V}
 
 with 
 
 
 
 
 |
 
 X
 
 |
 
 ≤
 k
 
 
 {\displaystyle |X|\leq k}
 
 such that, when all vertices of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 and their adjacent edges are deleted from 
 
 
 
 G
 
 
 {\displaystyle G}
 
, the remainder is <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycle-free</a>?
The graph 
 
 
 
 G
 [
 V
 ∖
 X
 ]
 
 
 {\displaystyle G[V\setminus X]}
 
 that remains after removing 
 
 
 
 X
 
 
 {\displaystyle X}
 
 from 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is an induced <a href="/facts/Forest_(graph_theory)/TCWk4Joy">forest</a> (resp. an induced <a href="/facts/Directed_acyclic_graph/k6zq1os9">directed acyclic graph</a> in the case of <a href="/facts/Directed_graph/YBdfQ0um">directed graphs</a>). 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 <a href="/facts/Directed_graph/YBdfQ0um">directed graphs</a>).

<h2 id="np-completeness">NP-completeness</h2>
Karp (1972) showed that finding a feedback vertex set of size 
 
 
 
 ≤
 k
 
 
 {\displaystyle \leq k}
 
 in <a href="/facts/Directed_graph/YBdfQ0um">directed graphs</a> is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>. 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.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
Karp's reduction also implies the NP-completeness of the feedback vertex set problem on undirected graphs, where the problem stays NP-complete on graphs of <a href="/facts/Degree_(graph_theory)/LnFFpI8v">maximum degree</a> four. The feedback vertex set problem can be solved in polynomial time on graphs of <a href="/facts/Degree_(graph_theory)/LnFFpI8v">maximum degree</a> at most three, using an algorithm based on the <a href="/facts/Matroid_parity_problem/7r8TLTQp">matroid parity problem</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="exact-algorithms">Exact algorithms</h2>
The corresponding <a href="/facts/NP_optimization_problem/PTcloS79">NP optimization problem</a> of finding the size of a minimum feedback vertex set can be solved in time O(1.7347n), where n is the number of vertices in the graph.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> 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 O(1.8638n).<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> The directed feedback vertex set problem can still be solved in time O*(1.9977n), where n is the number of vertices in the given directed graph.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> The parameterized versions of the directed and undirected problems are both <a href="/facts/Fixed-parameter_tractable/RoyaJGgJ">fixed-parameter tractable</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
In undirected graphs of maximum <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> three, the feedback vertex set problem can be solved in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>, by transforming it into an instance of the <a href="/facts/Matroid_parity_problem/7r8TLTQp">matroid parity problem</a> for <a href="/facts/Linear_matroid/bYHY9rx1">linear matroids</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="approximation">Approximation</h2>
The undirected problem is <a href="/facts/APX/ggqAJ3A3">APX-complete</a>. This follows from the following facts.

<ul><li>The APX-completeness of the <a href="/facts/Vertex_cover/WK86bJvf">vertex cover problem</a>;<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li>The existence of an approximation preserving <a href="/facts/L-reduction/k71t0luq">L-reduction</a> from the vertex cover problem to it;</li>
<li>Existing constant-factor approximation algorithms.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li></ul>
The best known approximation algorithm on undirected graphs is by a factor of two.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
By contrast, the directed version of the problem appears to be much harder to approximate. Under the <a href="/facts/Unique_games_conjecture/gDYzTfRG">unique games conjecture</a>, an unproven but commonly used <a href="/facts/Computational_hardness_assumption/ewjpb1I7">computational hardness assumption</a>, 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 <a href="/facts/Feedback_arc_set/p69AScPL">feedback arc set</a> problem,<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> but since the feedback arc set problem and feedback vertex set problem in directed graphs are reducible to one another while preserving solution sizes,<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> it also holds for the latter.

<h2 id="bounds">Bounds</h2>
According to the <a href="/facts/Erd%25C5%2591s%25E2%2580%2593P%25C3%25B3sa_theorem/3xjzzBfp">Erdős–Pósa theorem</a>, 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.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

<h2 id="related-concepts">Related concepts</h2>
<ul><li>Instead of vertices, one can consider a feedback edge set - 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 <a href="/facts/Circuit_rank/RqbfVDR6">circuit rank</a> of the graph. In contrast to the FVS number, the circuit rank can be easily computed: it is 
 
 
 
 
 |
 
 E
 
 |
 
 −
 
 |
 
 V
 
 |
 
 +
 
 |
 
 C
 
 |
 
 
 
 {\displaystyle |E|-|V|+|C|}
 
, where C is the set of <a href="/facts/Component_(graph_theory)/5owVSXtY">connected components</a> of the graph. The problem of finding a smallest feedback edge set is equivalent to finding a <a href="/facts/Spanning_tree/qQPN9taR">spanning forest</a>, which can be done in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>.</li>
<li>The analogous concept in a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> is the <a href="/facts/Feedback_arc_set/p69AScPL">feedback arc set</a> (FAS) - a set of directed arcs whose removal makes the graph acyclic. Finding a smallest FAS is an NP-hard problem.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a></li></ul>
<h2 id="applications">Applications</h2>
<ul><li>In <a href="/facts/Operating_system/8XTuvMh2">operating systems</a>, feedback vertex sets play a prominent role in the study of <a href="/facts/Deadlock_(computer_science)/YDpdfnPP">deadlock</a> recovery. In the <a href="/facts/Wait-for_graph/UGHplktM">wait-for graph</a> 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 abort.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a></li>
<li>The feedback vertex set problem has applications in <a href="/facts/VLSI/l1Wgqr27">VLSI</a> chip design.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a></li>
<li>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<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> and the path reconfiguration problem.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a></li></ul>
<h2 id="notes">Notes</h2>

<h3>Research articles</h3>

<ul><li>Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro (1999), "A 2-approximation algorithm for the undirected feedback vertex set problem", SIAM Journal on Discrete Mathematics, 12 (3): 289–297 (electronic), <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2FS0895480196305124">10.1137/S0895480196305124</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1710236">1710236</a>.</li>
<li>Becker, Ann; Bar-Yehuda, Reuven; Geiger, Dan (2000), "Randomized algorithms for the loop cutset problem", <a href="/facts/Journal_of_Artificial_Intelligence_Research/92NuDEDN">Journal of Artificial Intelligence Research</a>, 12: 219–234, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1106.0225">1106.0225</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1613%2Fjair.638">10.1613/jair.638</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1765590">1765590</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:10243677">10243677</a></li>
<li>Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.", <a href="/facts/Artificial_Intelligence_(journal)/bSIa7D9U">Artificial Intelligence</a>, 83 (1): 167–188, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.1442">10.1.1.25.1442</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0004-3702%2895%2900004-6">10.1016/0004-3702(95)00004-6</a></li>
<li>Cao, Yixin; Chen, Jianer; Liu, Yang (2010), "On feedback vertex set: new measure and new structures", in Kaplan, Haim (ed.), Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Norway, June 21-23, 2010, Lecture Notes in Computer Science, vol. 6139, pp. 93–104, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1004.1672">1004.1672</a>, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2010LNCS.6139...93C">2010LNCS.6139...93C</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-13731-0_10">10.1007/978-3-642-13731-0_10</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-13730-3</li>
<li>Chen, Jianer; Fomin, Fedor V.; Liu, Yang; Lu, Songjian; Villanger, Yngve (2008), "Improved algorithms for feedback vertex set problems", <a href="/facts/Journal_of_Computer_and_System_Sciences/cNek9ego">Journal of Computer and System Sciences</a>, 74 (7): 1188–1198, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.jcss.2008.05.002">10.1016/j.jcss.2008.05.002</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2454063">2454063</a></li>
<li>Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>, 55 (5), Art. 21, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1411509.1411511">10.1145/1411509.1411511</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2456546">2456546</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1547510">1547510</a></li>
<li><a href="/facts/Irit_Dinur/hBBcgrjE">Dinur, Irit</a>; Safra, Samuel (2005), <a href="https://web.archive.org/web/20090920071048/http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf">"On the hardness of approximating minimum vertex cover"</a> (PDF), <a href="/facts/Annals_of_Mathematics/CUYktUqD">Annals of Mathematics</a>, Second Series, 162 (1): 439–485, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4007%2Fannals.2005.162.439">10.4007/annals.2005.162.439</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2178966">2178966</a>, archived from <a href="http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf">the original</a> (PDF) on 2009-09-20, retrieved 2010-03-29</li>
<li><a href="/facts/Paul_Erd%25C5%2591s/63LoUTe1">Erdős, Paul</a>; <a href="/facts/Lajos_P%25C3%25B3sa_(mathematician)/jIECajdr">Pósa, Lajos</a> (1965), <a href="http://www.renyi.hu/~p_erdos/1965-05.pdf">"On independent circuits contained in a graph"</a> (PDF), <a href="/facts/Canadian_Journal_of_Mathematics/oHhVvs1V">Canadian Journal of Mathematics</a>, 17: 347–352, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4153%2FCJM-1965-035-8">10.4153/CJM-1965-035-8</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:123981328">123981328</a></li>
<li>Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "On the minimum feedback vertex set problem: exact and enumeration algorithms.", <a href="/facts/Algorithmica/EqSt27Q2">Algorithmica</a>, 52 (2): 293–307, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.722.8913">10.1.1.722.8913</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00453-007-9152-0">10.1007/s00453-007-9152-0</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:731997">731997</a></li>
<li>Fomin, Fedor V.; Villanger, Yngve (2010), "Finding induced subgraphs via minimal triangulations", Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, pp. 383–394, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4230%2FLIPIcs.STACS.2010.2470">10.4230/LIPIcs.STACS.2010.2470</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9783939897163, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:436224">436224</a></li>
<li><a href="/facts/Richard_Karp/XtYCL0nA">Karp, Richard M.</a> (1972), "Reducibility Among Combinatorial Problems", Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103</li>
<li>Li, Deming; Liu, Yanpei (1999), "A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph", Acta Mathematica Scientia, 19 (4): 375–381, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fs0252-9602%2817%2930520-9">10.1016/s0252-9602(17)30520-9</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1735603">1735603</a></li>
<li>Razgon, I. (2007), "Computing minimum directed feedback vertex set in O*(1.9977n)", in <a href="/facts/Giuseppe_F._Italiano/QKsY5lt9">Italiano, Giuseppe F.</a>; Moggi, Eugenio; Laura, Luigi (eds.), <a href="http://www.cs.le.ac.uk/people/ir45/papers/ictcsIgorCamera.pdf">Proceedings of the 10th Italian Conference on Theoretical Computer Science</a> (PDF), World Scientific, pp. 70–81</li>
<li>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", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 72 (1–3): 355–360, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2888%2990226-9">10.1016/0012-365X(88)90226-9</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0975556">0975556</a></li></ul>

<h3>Textbooks and survey articles</h3>
<ul><li>Festa, P.; Pardalos, P. M.; <a href="/facts/Mauricio_Resende/RBP1VI8a">Resende, M.G.C.</a> (2000), "Feedback set problems", in Du, D.-Z.; Pardalos, P. M. (eds.), <a href="http://www.research.att.com/~mgcr/doc/sfsp.pdf">Handbook of Combinatorial Optimization, Supplement vol. A</a> (PDF), Kluwer Academic Publishers, pp. 209–259</li>
<li><a href="/facts/Michael_R._Garey/xuSLYs90">Garey, Michael R.</a>; <a href="/facts/David_S._Johnson/kGSBxucb">Johnson, David S.</a> (1979), <a href="/facts/Computers_and_Intractability%3a_A_Guide_to_the_Theory_of_NP-Completeness/04FE56Ss">Computers and Intractability: A Guide to the Theory of NP-Completeness</a>, W.H. Freeman, <a href="https://archive.org/details/computersintract0000gare/page/">A1.1: GT7, p. 191</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-7167-1045-5</li>
<li>Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-470-12872-5</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">unpublished results due to Garey and Johnson, cf. Garey & Johnson (1979): GT7 - Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A1.1: GT7, p. 191, ISBN 978-0-7167-1045-5 <a href="https://archive.org/details/computersintract0000gare/page/" target="_blank">https://archive.org/details/computersintract0000gare/page/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Ueno, Kajitani & Gotoh (1988); Li & Liu (1999) - 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", Discrete Mathematics, 72 (1–3): 355–360, doi:10.1016/0012-365X(88)90226-9, MR 0975556 <a href="https://doi.org/10.1016%2F0012-365X%2888%2990226-9" target="_blank">https://doi.org/10.1016%2F0012-365X%2888%2990226-9</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Fomin & Villanger (2010) - Fomin, Fedor V.; Villanger, Yngve (2010), "Finding induced subgraphs via minimal triangulations", Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, pp. 383–394, doi:10.4230/LIPIcs.STACS.2010.2470, ISBN 9783939897163, S2CID 436224 <a href="https://doi.org/10.4230%2FLIPIcs.STACS.2010.2470" target="_blank">https://doi.org/10.4230%2FLIPIcs.STACS.2010.2470</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Fomin et al. (2008). - Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "On the minimum feedback vertex set problem: exact and enumeration algorithms.", Algorithmica, 52 (2): 293–307, CiteSeerX 10.1.1.722.8913, doi:10.1007/s00453-007-9152-0, S2CID 731997 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.722.8913" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.722.8913</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Razgon (2007). - Razgon, I. (2007), "Computing minimum directed feedback vertex set in O*(1.9977n)", in Italiano, Giuseppe F.; Moggi, Eugenio; Laura, Luigi (eds.), Proceedings of the 10th Italian Conference on Theoretical Computer Science (PDF), World Scientific, pp. 70–81 <a href="http://www.cs.le.ac.uk/people/ir45/papers/ictcsIgorCamera.pdf" target="_blank">http://www.cs.le.ac.uk/people/ir45/papers/ictcsIgorCamera.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Chen et al. (2008). - Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM, 55 (5), Art. 21, doi:10.1145/1411509.1411511, MR 2456546, S2CID 1547510 <a href="https://doi.org/10.1145%2F1411509.1411511" target="_blank">https://doi.org/10.1145%2F1411509.1411511</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Ueno, Kajitani & Gotoh (1988). - 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", Discrete Mathematics, 72 (1–3): 355–360, doi:10.1016/0012-365X(88)90226-9, MR 0975556 <a href="https://doi.org/10.1016%2F0012-365X%2888%2990226-9" target="_blank">https://doi.org/10.1016%2F0012-365X%2888%2990226-9</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Dinur & Safra 2005 - Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics, Second Series, 162 (1): 439–485, doi:10.4007/annals.2005.162.439, MR 2178966, archived from the original (PDF) on 2009-09-20, retrieved 2010-03-29 <a href="https://web.archive.org/web/20090920071048/http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf" target="_blank">https://web.archive.org/web/20090920071048/http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Karp (1972) - Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103 <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Becker & Geiger (1996). See also Bafna, Berman & Fujito (1999) for an alternative approximation algorithm with the same approximation ratio. - Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.", Artificial Intelligence, 83 (1): 167–188, CiteSeerX 10.1.1.25.1442, doi:10.1016/0004-3702(95)00004-6 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.1442" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.1442</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Guruswami, Venkatesan; Manokaran, Rajsekar; Raghavendra, Prasad (2008). "Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. pp. 573–582. doi:10.1109/FOCS.2008.51. ISBN 978-0-7695-3436-7. S2CID 8762205. <a href="978-0-7695-3436-7" target="_blank">978-0-7695-3436-7</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Even, G.; (Seffi) Naor, J.; Schieber, B.; Sudan, M. (1998). "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs". Algorithmica. 20 (2): 151–174. doi:10.1007/PL00009191. ISSN 0178-4617. S2CID 2437790. <a href="http://link.springer.com/10.1007/PL00009191" target="_blank">http://link.springer.com/10.1007/PL00009191</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Erdős & Pósa (1965). - Erdős, Paul; Pósa, Lajos (1965), "On independent circuits contained in a graph" (PDF), Canadian Journal of Mathematics, 17: 347–352, doi:10.4153/CJM-1965-035-8, S2CID 123981328 <a href="http://www.renyi.hu/~p_erdos/1965-05.pdf" target="_blank">http://www.renyi.hu/~p_erdos/1965-05.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Karp (1972) - Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103 <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Silberschatz, Galvin & Gagne (2008). - Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5 <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Festa, Pardalos & Resende (2000). - Festa, P.; Pardalos, P. M.; Resende, M.G.C. (2000), "Feedback set problems", in Du, D.-Z.; Pardalos, P. M. (eds.), Handbook of Combinatorial Optimization, Supplement vol. A (PDF), Kluwer Academic Publishers, pp. 209–259 <a href="http://www.research.att.com/~mgcr/doc/sfsp.pdf" target="_blank">http://www.research.att.com/~mgcr/doc/sfsp.pdf</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Kratsch, Stefan; Schweitzer, Pascal (2010). "Isomorphism for Graphs of Bounded Feedback Vertex Set Number". In Kaplan, Haim (ed.). Algorithm Theory - SWAT 2010. Lecture Notes in Computer Science. Vol. 6139. Berlin, Heidelberg: Springer. pp. 81–92. Bibcode:2010LNCS.6139...81K. doi:10.1007/978-3-642-13731-0_9. ISBN 978-3-642-13731-0. <a href="978-3-642-13731-0" target="_blank">978-3-642-13731-0</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Algorithms and Data Structures (PDF). Lecture Notes in Computer Science. Vol. 11646. 2019. doi:10.1007/978-3-030-24766-9. ISBN 978-3-030-24765-2. S2CID 198996919. <a href="978-3-030-24765-2" target="_blank">978-3-030-24765-2</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
</ol>

Feedback vertex set open-in-new

Feedback vertex set