Constant-factor hardness of directed feedback vertex set

For every fixed \(\varepsilon,\delta\in(0,1/2)\), there are an integer
\(s\ge1\) and a deterministic polynomial-time reduction from
\(\mathrm{3SAT}\) to explicit unweighted Unique Games instances
\(G_\varphi\) over \(K=\F_2^s\) such that
\[
\begin{aligned}
 \varphi\text{ satisfiable}
 &\quad\Longrightarrow\quad \val(G_\varphi)\ge1-\varepsilon,\\
 \varphi\text{ unsatisfiable}
 &\quad\Longrightarrow\quad \val(G_\varphi)\le\delta.
\end{aligned}
\]
The graph is simple and bipartite, and every constraint is a translation
\(a(v_e)=a(u_e)+c_e\) of \(K\). The alphabet, the degree of the
running-time polynomial, and its constants depend only on
\(\varepsilon,\delta\).

For every fixed $\alpha$ with $\GW<\alpha\le1$, it is NP-hard to approximate
Max-Cut within a factor of $\alpha$. This holds for simple unweighted graphs.

Fix a rational $t\in(0,1)$ and a constant
$0<\eps<(t-B(t))/4$. For graphs equipped with a rational probability
distribution on edges, it is NP-hard to distinguish
\begin{align*}
 \textnormal{YES:}\quad&\Val\ge\frac{1+t}{2}-\eps,\\
 \textnormal{NO:}\quad&\Val\le\frac{1+B(t)}{2}+\eps,
\end{align*}
where $\Val$ is the maximum cut weight.

For every fixed integer \(m\geq4\), there is a deterministic
polynomial-time reduction from \(\mathrm{3SAT}\) to finite simple
undirected unweighted graphs with the following guarantees:
\[
\begin{array}{ll}
\text{the formula is satisfiable}
 &\Longrightarrow\quad
 \tau(G)<\left(\dfrac12+\dfrac1m\right)|V(G)|,\\[6pt]
\text{the formula is unsatisfiable}
 &\Longrightarrow\quad
 \tau(G)>\left(1-\dfrac1m\right)|V(G)|.
\end{array}
\]
The output lists all vertices and edges explicitly.

For every fixed real \(\alpha\) with \(1\leq\alpha<2\),
approximating Vertex Cover within factor \(\alpha\) is NP-hard.
Thus, unless \(\mathrm P=\mathrm{NP}\), no deterministic
polynomial-time algorithm achieves factor \(2-\varepsilon\)
for any fixed \(\varepsilon\in(0,1]\).

For every fixed integer $K\ge2$, there is a deterministic polynomial-time
many-one reduction mapping a $3$SAT formula $\varphi$ to a pair $(G,k)$, where
$G$ is an explicit finite simple undirected unweighted graph and $k\ge1$ is
a binary-encoded integer, such that
\[
 \begin{aligned}
 \varphi\text{ satisfiable}&\quad\Longrightarrow\quad
       \OPT_{\rm uncut}(G)\le k,\\
 \varphi\text{ unsatisfiable}&\quad\Longrightarrow\quad
       \OPT_{\rm uncut}(G)>Kk.
 \end{aligned}
\]
For each fixed $K$, the graph size, full construction work, and bit complexity
are polynomial in the bit length of $\varphi$. All constants are effective;
no advice or oracle is supplied to the reduction.

For every fixed real $C>1$, minimum $2$CNF clause deletion is NP-hard to
approximate within factor $C$. In particular, a deterministic polynomial-time
$C$-approximation would imply $\mathsf P=\NP$.

For every fixed real constant $A\ge1$, 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\in\N_{>0}$. The polynomial and its constants may depend on $A$.
The reduction has the following alternatives:
\[
  \textnormal{YES: }\DFVS(G)\le k,
  \qquad
  \textnormal{NO: }\DFVS(G)>Ak.
\]