Constant-factor hardness of directed feedback vertex set
For every fixed real constant , it is NP-hard to approximate minimum directed feedback vertex set within factor on unweighted digraphs, via a deterministic polynomial-time reduction from an NP-hard promise problem to instances with such that in the YES case and in the NO case.
The proof of Theorem 1.1 on page 28 validly combines Propositions 3.6, 3.7, 7.4, and Lemma 8.1, and all supporting steps are rigorously proved in the manuscript.
“Theorem 1.1. For every fixed real constant A ≥ 1, it is NP-hard to approximate minimum directed feedback vertex set within factor A on unweighted digraphs. More precisely, there is a deterministic polynomial-time reduction from an NP-hard promise problem to instances (G, k) with k ∈ N>0. The polynomial and its constants may depend on A. The reduction has the following alternatives: YES: DFVS(G) ≤ k, NO: DFVS(G) > Ak.” · Show in paper