==== TABLE OF CONTENTS ====
Constant-factor-hardness-of-directed-feedback-vertex-set//construction.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//introduction.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//main.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//pivotality.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//prefix-refinement.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//prefix.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//preliminaries.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//ranks.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//soundness.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//unweighting.tex
Constant-factor-hardness-of-directed-feedback-vertex-set//references.bib
===========================
==== BEGIN Constant-factor-hardness-of-directed-feedback-vertex-set//construction.tex ====
\section{The weighted reduction}
\label{sec:construction}
We first construct a digraph with positive rational vertex costs. Write
$w_v$ for the cost of a vertex $v$ and $w(F)=\sum_{v\in F}w_v$ for the cost
of a vertex set $F$. For each
fixed integer $A\ge 1$, the construction will have a feedback vertex set of
cost at most $4$ in the completeness case of Theorem~\ref{thm:games}, whereas
every feedback vertex set will have cost greater than $D=10A$ in its soundness
case. Section~\ref{sec:unweighting} converts this gap into an unweighted one.
\subsection{Choice of parameters}
\label{sec:parameters}
Fix an integer $A\ge 1$ and put $D=10A$. The constants have the following
roles. There will be $M$ bias scales and at most $T$ prefix slots.
The full-prefix and comparison tests have total costs $H$ and $K$.
The junta size is bounded by $J$, independently of the game alphabets;
$\theta$ is the required game accuracy. Finally $L$ and $N$ specify
finite ordered rank sets, and $\psi:[L]\hookrightarrow[N]$ is an
increasing random embedding. Its purpose is to make the order
comparisons insensitive to their precise rank levels, as proved in
Lemma~\ref{lem:rank-spreading}.
Choose the constants in the following order.
\begin{enumerate}[label=\arabic*.]
\item Set
\[
M=128(D+1),\qquad
p_i=2^{-(i+1)},\qquad q_i=2p_i\quad (i\in[M]),
\qquad \gamma=\frac{p_M}{1000}.
\]
\item Set $H=8(D+1)$. Choose an integer $T\ge 1$ large enough that
\begin{equation}
HM\exp\left(-\frac{p_MT}{8M}\right)\le 1,
\label{eq:prefix-length-choice}
\end{equation}
and an integer
\begin{equation}
K\ge \frac{M2^T D}{\gamma}.
\label{eq:comparison-mass-choice}
\end{equation}
\item Put $B_0=(D+1)/\gamma$. By Corollary~\ref{cor:dyadic-junta}, there
is an integer $J\ge 1$ that bounds the size of a junta approximant with
error at most $\gamma$ for every function of total influence at most $B_0$
at any of the biases $p_i,q_i$, $i\in[M]$. Choose a positive rational
$\theta$ small enough that Theorem~\ref{thm:games} applies and
\begin{equation}
K\theta\le 1,\qquad J^2\theta\le\gamma.
\label{eq:game-accuracy-choice}
\end{equation}
Apply that theorem with this fixed $\theta$, and let $X,Y$ be its
alphabets, with $m=\abs{X}=2\abs{Y}$.
\item Put
\[
k_{\max}=2^Tm,\qquad L=10k_{\max}+30,
\qquad \rho=\min\{\gamma,1/m\}.
\]
Choose a positive rational $\eta$ satisfying
\begin{equation}
3\eta L^3 2^{m^T}\le\rho.
\label{eq:rank-accuracy-choice}
\end{equation}
Apply Lemma~\ref{lem:rank-spreading} to $L,\eta$, obtaining a finite $N$
and a rational probability distribution on increasing maps
$\psi:[L]\hookrightarrow[N]$. Fix this distribution for the construction.
\end{enumerate}
All these quantities depend only on $A$. In particular, the junta bound
$J$ is fixed \emph{before} the alphabet size $m$ is determined. Its existence
does not require an alphabet bound. The later choices of $\rho,\eta,N$
therefore introduce no dependence back into the choice of $\theta$.
Let the input game have bipartition $U,V$, edge distribution $\nu$, and
endpoint marginals $\nu_U,\nu_V$. For an edge $e=(u,v)$, write
$\pi_e:X\to Y$ for its two-to-one projection. All probability distributions
below are finite and rational. A sampling description specifies a separate
vertex for each outcome of positive probability, with the indicated
probability as a factor in its cost. The reduction enumerates these outcomes;
it does not sample a random output graph.
\subsection{Rank vertices and their identifications}
\begin{definition}[Rank graph]
\label{def:rank-graph}
For $w\in U\cup V$, let $\Lambda_w=X$ if $w\in U$ and $\Lambda_w=Y$ if
$w\in V$, and put $m_w=\abs{\Lambda_w}$. The allowed vertex tuples are
\[
\bigcup_{t=0}^{T}U^t
\quad\cup\quad
\bigcup_{t=0}^{T-1}(U^t\times V).
\]
Tuples are ordered sequences and may contain repeated vertices. For an
allowed tuple $\mathbf d=(w_1,\ldots,w_t)$, let
$\Lambda_{\mathbf d}=\prod_{j=1}^t\Lambda_{w_j}$; the product for the empty
tuple is a singleton. In every case
\begin{equation}
\abs{\Lambda_{\mathbf d}}\le m^T.
\label{eq:tuple-domain-bound}
\end{equation}
For every function $x:\Lambda_{\mathbf d}\to[N]$, introduce a formal rank
vertex $b_{\mathbf d}(x)$. Within each tuple, introduce an arc
$b_{\mathbf d}(x)\to b_{\mathbf d}(y)$ whenever
\[
x(\lambda)z_\ell
\quad\text{for all }\ell\in[k]
\text{ and }\lambda\in C_\ell\setminus Z.
\label{eq:wildcard-outgoing}
\end{equation}
There are no restrictions on the values of $x$ on $Z$.
\end{definition}
The wildcard inequalities have a direct interpretation under any global
labeling. If its evaluated tuple lies in $C_r\setminus Z$, the threshold
$z_r$ lies strictly between the evaluations of every incoming and every
outgoing rank vertex. Assigning that threshold to the test therefore extends
the increasing evaluation along its incident arcs. At starred tuples, the
arc conditions impose no restriction on these evaluated values; the
completeness argument will delete the corresponding test.
\begin{definition}[Prefix data]
\label{def:prefix-data}
For $t\in\{0,\ldots,T\}$, draw
$\mathbf s=(u_1,\ldots,u_t)$ independently from $\nu_U$ in each slot.
Independently draw $i_1,\ldots,i_t$ uniformly from $[M]$. Conditional on
these indices, draw $P_j\subseteq X$ using independent Bernoulli
$p_{i_j}$ membership bits, independently for different slots $j$.
Partition $\Lambda_{\mathbf s}$ by the membership patterns
\[
\bigl(\ind{\lambda_j\in P_j}\bigr)_{j=1}^t,
\qquad \lambda\in\Lambda_{\mathbf s}.
\]
Order the $2^t$ cells lexicographically with $1$ before $0$, keeping cells
that happen to be empty, and denote them by $C_1,\ldots,C_{2^t}$. Put
\[
C_{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.
\]
\end{theorem}
Theorem~\ref{thm:main} implies that a deterministic polynomial-time
algorithm with any constant approximation guarantee exists if and
only if $\mathrm P=\mathrm{NP}$. For the reverse implication, membership
of the size-bounded decision problem in NP permits exact optimization
and witness search when $\mathrm P=\mathrm{NP}$. The theorem establishes
that the required approximation factor grows without bound with the
input size, assuming $\mathrm P\ne\mathrm{NP}$. It does not identify
that growth rate or improve the general approximation algorithm.
A directed feedback arc set is a set of arcs whose deletion leaves an
acyclic digraph. Corollary~\ref{cor:feedback-arc} transfers the same
hardness to this problem on unweighted simple loopless digraphs, through
a reduction preserving both the optimum and approximation solutions.
The vertex-set hardness also holds when opposite arcs are forbidden,
as shown in Remark~\ref{rem:no-opposite-arcs}.
\subsection{Methodological background}
Our construction shares the useful division between protected vertices
and deletable test vertices in Svensson's dictatorship gadget
\cite[Section~3.1.1]{Svensson2013}. His soundness proof also reads a
Boolean function from a topological order
\cite[Section~3.1.3]{Svensson2013}. Here the protected vertices encode
rank profiles, and compatibility across tuple prefixes supplies a
family of monotone functions. Svensson uses the ``It Ain't Over Till
It's Over'' theorem; Guruswami and Lee instead use an invariance
principle \cite[Section~1]{GuruswamiLee2016}. Our analytic input is
Friedgut's theorem on Boolean functions of bounded total influence
\cite{Friedgut1998}. We derive its required fixed-bias form explicitly.
Junta-based label decoding already appears in Dinur and Safra's
Vertex Cover hardness proof \cite[Sections~1.1 and~3]{DinurSafra2005},
where a nearby bias is selected to obtain bounded total influence.
Here a single pivotality budget controls all the prescribed biases,
and the contradiction requires their estimates to concern the same
distribution of functions.
The rank distribution is obtained by combining finite Ramsey theory
\cite{Ramsey1930} with finite minimax \cite{vonNeumann1928}.
These are the external combinatorial tools in the rank-spreading
argument. The shared-prefix construction and the permutation
pivotality budget are proved below. Their role is to compare many
biases without changing the distribution of the functions being
analyzed. The source of hardness is the published imperfect-completeness
two-to-one theorem, so the proof does not consume a Unique Games
hardness theorem.
\subsection{The reduction and its new ingredients}
A two-to-one game has a bipartite constraint graph with a label set
$X$ at each big-side vertex and a label set $Y$ at each small-side
vertex. Each edge carries a map $X\to Y$ with exactly two preimages
per label; an edge is satisfied when the chosen endpoint labels obey
that map. The game value is the largest fraction of satisfied edges,
measured under its prescribed edge distribution.
Our starting point is the imperfect-completeness 2-to-1 Games Theorem,
obtained through the work of Dinur, Khot, Kindler, Minzer, and Safra,
Khot, Minzer, and Safra, and Barak, Kothari, and Steurer
\cite{DKKMS2025,KMS2018,BKS2019}. We use its precise form in
Theorem~\ref{thm:games}: for arbitrarily small constant $\theta>0$,
distinguishing game value at least $1-\theta$ from value at most
$\theta$ is NP-hard, with fixed alphabets and exact two-element
projection fibers. The perfect-completeness 2-to-1 Games Conjecture
is not a premise of the argument.
The central difficulty is to extract a game labeling from an arbitrary
acyclic remainder. An acyclic graph supplies a topological order, but
its order can interleave the many vertices representing the same local
test. The proof first makes comparisons within that order consistent,
then interprets them as Boolean functions. Small deletion cost will
constrain these functions in incompatible ways.
For a fixed integer factor $A$, put $D=10A$. We construct a weighted
graph with a feedback vertex set of cost at most $4$ in the YES case.
Suppose, toward the soundness contradiction, that a NO instance has
one of cost at most $D$. Fix a topological order after its deletion.
The following four steps analyze this arbitrary order. A Boolean
function on subsets is evaluated at bias $p$ by including each label
independently with probability $p$; its acceptance is the probability
that its value is one.
\begin{enumerate}[label=\textup{(\arabic*)}]
\item \emph{Rank comparisons with a common interpretation.}
For each short tuple of game vertices, we create vertices indexed by
rank-valued functions of label tuples. A global labeling evaluates
all these functions consistently. In the soundness analysis, a
putative inexpensive feedback set leaves every rank vertex present,
so its surviving topological order supplies comparison bits. A
finite Ramsey and minimax argument produces a distribution on rank
embeddings for which all triples of positions have nearly identical
image laws. Ordered comparisons then agree with high probability,
yielding a monotone Boolean function of subsets of label tuples.
\item \emph{Conditioning through a shared prefix.}
Successive random subsets split label tuples into lexicographically
ordered cells. Monotonicity selects a unique transition cell, and
prefix identifications make these transitions consistent under
refinement. A full-prefix test prevents the chosen cell from having
too few membership-one steps at any of many dyadic biases. On
averaging, the conditioned big-side Boolean function has acceptance
at least a constant multiple of the bias at every scale. The same
prefix data define functions for every game vertex before a fresh
constraint is drawn.
\item \emph{A pivotality budget independent of the alphabet size.}
A single-label test charges the event that the starred label can be
pivotal somewhere along a random permutation. The resulting quantity $B(f)$ is the sum, over labels, of the
probability that the label is pivotal at some prefix of a random
permutation of the other labels. It bounds both total influence and
acceptance probability divided by the bias, at every bias. Its
expectation is at most $D+1$ on either side of the game. Friedgut's junta theorem \cite{Friedgut1998}, transferred
to fixed dyadic biases, therefore supplies bounded coordinate lists
outside a small exceptional set. Their size is fixed before choosing
the game alphabets.
\item \emph{A common tail variable across all scales.}
A projection-respecting coupling compares bias $p$ on the big side
with bias $2p$ on the small side. Game soundness makes the two junta
lists typically use disjoint projection fibers. The corresponding
outputs are then independent under the coupling, allowing the
comparison bound to pass to product measures. At each dyadic bias, this forces a positive contribution of constant
size to the tail sum of the small-side pivotality budget. All these
estimates concern the same random variable under the same distribution.
Adding sufficiently many such contributions contradicts its expected
budget.
\end{enumerate}
The pivotality quantity is independent of the bias. This is essential:
a separate influence bound at each scale would not justify adding the
contributions to one tail sum. Likewise, the shared prefix fixes all
vertex functions before the tested game edge is drawn; otherwise the
coordinate lists would not define a game labeling.
The proof uses finite probability spaces to specify weighted test
families. Every outcome is included explicitly with its probability
as part of its cost. Thus the reduction is deterministic. All
parameters, alphabets, tuple lengths, and rank tables are constants
once the target factor is fixed, even though some are extremely
large. Finally, rounding each vertex cost upward and replacing a
vertex by an independent cluster produces an unweighted gap.
\subsection{Organization}
Section~\ref{sec:preliminaries} states the external theorems and proves
the required dyadic junta corollary.
Section~\ref{sec:construction} gives the parameter choices, graph,
tests, and completeness argument. Section~\ref{sec:ranks} proves rank
spreading and the order lemmas used to read Boolean functions from a
surviving graph. Sections~\ref{sec:prefix} and~\ref{sec:pivotality}
establish the acceptance lower bounds and pivotality budgets.
Section~\ref{sec:soundness} gives the comparison and tail-sum
contradiction. Section~\ref{sec:unweighting} removes the costs and
proves Theorem~\ref{thm:main}.
==== END Constant-factor-hardness-of-directed-feedback-vertex-set//introduction.tex ====
==== BEGIN Constant-factor-hardness-of-directed-feedback-vertex-set//main.tex ====
\newcommand{\DoNotLoadEpstopdf}{}
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{enumitem,booktabs,microtype,xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning}
\usepackage{hyperref}
\hypersetup{pdftitle={Constant-factor hardness of directed feedback vertex set},pdfauthor={OpenAI},colorlinks=true,linkcolor=blue!50!black,citecolor=blue!50!black,urlcolor=blue!50!black}
\AddToHook{cmd/thebibliography/after}{\addcontentsline{toc}{section}{\refname}}
\ifdefined\pdftrailerid\pdftrailerid{}\fi
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\numberwithin{equation}{section}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\E}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\DeclareMathOperator{\DFVS}{DFVS}
\DeclareMathOperator{\TV}{TV}
\newcommand{\ind}[1]{\mathbf 1\{#1\}}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\norm}[1]{\lVert#1\rVert}
\setlist{itemsep=3pt,topsep=5pt}
\title{Constant-factor hardness of\\directed feedback vertex set}
\author{OpenAI}
\date{September 23, 2026}
\begin{document}
\maketitle
\begin{abstract}
Approximating minimum directed feedback vertex set within any fixed
constant factor is NP-hard, even on unweighted digraphs.
\end{abstract}
\tableofcontents
\input{sections/introduction}
\input{sections/preliminaries}
\input{sections/construction}
\input{sections/ranks}
\input{sections/prefix}
\input{sections/pivotality}
\input{sections/soundness}
\input{sections/unweighting}
\bibliographystyle{plain}
\par
\begingroup
\small
\bibliography{references}
\endgroup
\end{document}
==== END Constant-factor-hardness-of-directed-feedback-vertex-set//main.tex ====
==== BEGIN Constant-factor-hardness-of-directed-feedback-vertex-set//pivotality.tex ====
\section{A budget for pivotal labels}
\label{sec:pivotality}
We associate to each conditioned function a quantity that controls both its
influences and its acceptance probabilities at every bias. The single-label
tests bound the expectation of this quantity under the common distribution
from Section~\ref{sec:prefix}.
A single test vertex may have several cuts that force its deletion, but its
cost is paid only once. Accordingly, we record whether a label is pivotal
somewhere along a permutation, rather than the number of witnessing prefixes.
\begin{definition}[Pivotality budget]
\label{def:pivotal-budget}
Let $S$ be a nonempty finite set, and let
$f:2^S\to\{0,1\}$ be monotone with $f(\varnothing)=0$ and $f(S)=1$.
For each $j\in S$, let $\sigma_j$ be a uniform permutation of
$S\setminus\{j\}$. Write $R_a(\sigma_j)$ for the set of its first $a$
elements, where $0\le a\le |S|-1$. Define
\[
B(f)=\sum_{j\in S}
\Pr_{\sigma_j}\!\left[
\begin{gathered}
\text{there exists }a\in\{0,\ldots,|S|-1\}\text{ such that}\\
f(R_a(\sigma_j))=0,\quad
f(R_a(\sigma_j)\cup\{j\})=1
\end{gathered}
\right].
\]
Thus both the empty prefix and the full prefix $S\setminus\{j\}$ are
allowed. A permutation contributes only once for a given $j$, even when
several of its prefixes witness pivotality. In particular,
$0\le B(f)\le |S|$.
\end{definition}
\begin{lemma}[Arrival-time inequalities]
\label{lem:pivotal-inequalities}
For every function in Definition~\ref{def:pivotal-budget} and every
$0=Stealth,
cell/.style={draw,rounded corners=2pt,minimum width=1.35cm,
minimum height=.65cm,font=\small},
chosen/.style={cell,fill=blue!10,draw=blue!60!black}]
\node[cell] (root) at (0,2.6) {$\Lambda_{\varnothing}$};
\node[chosen] (one) at (-1.2,1.3) {$1$};
\node[cell] (zero) at (1.2,1.3) {$0$};
\node[cell] (oo) at (-1.8,0) {$11$};
\node[chosen] (oz) at (-.6,0) {$10$};
\node[cell] (zo) at (.6,0) {$01$};
\node[cell] (zz) at (1.8,0) {$00$};
\foreach \a/\b in {root/one,root/zero,one/oo,one/oz,zero/zo,zero/zz}
\draw[->] (\a)--(\b);
\node[font=\small,anchor=west] at (2.4,1.3) {membership pattern};
\node[font=\small,anchor=west] at (2.4,-.75) {cumulative bit};
\foreach \x/\b in {-1.8/0,-.6/1,.6/1,1.8/1}
\node[font=\small] at (\x,-.75) {$\b$};
\draw[->,blue!60!black] (-1.25,-.75)--(-1.05,-.75);
\end{tikzpicture}
\caption{Schematic transition refinement for two prefix slots. Membership
$1$ precedes $0$ lexicographically. In the illustrated case the cumulative
bit changes at cell $10$, so the transition is in the first cell at depth
one and its second child at depth two. The selected membership bits are
therefore $f_{u_1,\mathcal D_0}(P_1)=1$ and $f_{u_2,\mathcal D_1}(P_2)=0$, with each function using
its preceding prefix. Empty cells are retained in the ordering but cannot
contain a transition.}
\label{fig:prefix-refinement}
\end{figure}
==== END Constant-factor-hardness-of-directed-feedback-vertex-set//prefix-refinement.tex ====
==== BEGIN Constant-factor-hardness-of-directed-feedback-vertex-set//prefix.tex ====
\section{Shared prefix conditioning}
\label{sec:prefix}
Continue to fix the feedback vertex set $F$ of cost at most $D$ and the
topological order $\prec$ from Section~\ref{sec:ranks}. When we sample graph
tests or their defining data below, we use the finite laws that define the
graph. In particular, the order is fixed before these
draws; the distribution of an embedding is not conditioned on whether any
test vertex survives.
We first specify a distribution that will be used at every bias scale.
Draw $\psi$ from the rank-spreading law. Independently choose $t$ uniformly
from $\{0,\ldots,T-1\}$ and draw the prefix data of length $t$ from
Definition~\ref{def:prefix-data}. Thus
$\mathbf s=(u_1,\ldots,u_t)$ has independent coordinates with law $\nu_U$,
the indices $i_1,\ldots,i_t$ are independent and uniform in $[M]$, and,
conditionally on these indices, the sets $P_j$ are independent with laws
$\mu_{p_{i_j}}^X$. Write
\begin{equation}
\mathcal D
=\bigl(\psi,t,\mathbf s,(i_j,P_j)_{j=1}^t\bigr)
\label{eq:common-conditioning}
\end{equation}
for these shared data. Independently draw an edge $e=(u,v)$ with law
$\nu$. Unless another experiment is explicitly specified, expectations
and probabilities involving sampled endpoints refer to this joint law of
$(\mathcal D,e)$. In particular, its marginal law for $(\mathcal D,u)$
is obtained by drawing $u\sim\nu_U$ independently of $\mathcal D$; the
corresponding statement holds for $v\sim\nu_V$.
\begin{definition}[Conditioned functions]
\label{def:conditioned-functions}
For each game vertex $w$, fix a label
$\lambda_w^\circ\in\Lambda_w$ independently of all the sampled data.
Given $\mathcal D$, let $C_1,\ldots,C_{2^t}$ be its ordered prefix
partition. If $\mathbf s$ is good, define its transition index by
\[
r_*=\min\{r:g_{\mathbf s}(C_{\le r})=1\}.
\]
For every $w\in U\cup V$ define a function on $2^{\Lambda_w}$ by
\[
f_w(R)=
\begin{cases}
g_{\mathbf s w}\bigl(E_w^{r_*}(R)\bigr),
&\text{if $\mathbf s w$ is good},\\
\ind{\lambda_w^\circ\in R},
&\text{otherwise},
\end{cases}
\]
where, as in Equation~\eqref{eq:comparison-sets},
\[
E_w^r(R)
=(C_{0\), there is a finite integer
\(J_{\mathrm{unif}}(b,\alpha)\) with the following property.
For every finite \(S\) and every Boolean function
\(f:2^S\to\{0,1\}\) with \(I_{1/2}(f)\le b\), there is a Boolean
function \(\widetilde f\), depending on at most
\(J_{\mathrm{unif}}(b,\alpha)\) coordinates, for which
\[
\Pr_{R\sim\mu_{1/2}^{S}}[\,f(R)\ne\widetilde f(R)\,]\le\alpha.
\]
The bound is independent of \(\abs S\).
\end{theorem}
This is the uniform version of Friedgut's theorem
\cite[Theorem~1.1 in the February 3, 1998 author manuscript]{Friedgut1998}.
Friedgut also proves a biased-product version
\cite[Theorem~4.1 in the same manuscript]{Friedgut1998}.
We give an elementary reduction of the dyadic case to the uniform case,
so that the dependence on the bias and independence of the game
alphabet size are explicit.
\begin{corollary}[Dyadic junta approximation]
\label{cor:dyadic-junta}
Let \(p=2^{-k}\), where \(k\ge1\) is an integer. For every \(b\ge0\)
and \(\alpha>0\), there is a finite integer \(J(p,b,\alpha)\),
independent of \(\abs S\), such that every Boolean function
\(f:2^S\to\{0,1\}\) with \(I_p(f)\le b\) has a Boolean junta
approximant on at most \(J(p,b,\alpha)\) coordinates with error at
most \(\alpha\) under \(\mu_p^S\).
\end{corollary}
\begin{proof}
The assertion is immediate for \(S=\varnothing\), so assume otherwise.
Let \((X_{j,a})_{j\in S,\,a\in[k]}\) be independent uniform bits and
put
\[
Z_j=\bigwedge_{a=1}^k X_{j,a},
\qquad
F(X)=f(\{j\in S:Z_j=1\}).
\]
The \(Z_j\) are independent Bernoulli \(p\) bits. Flipping \(X_{j,a}\)
changes \(F\) precisely when all the other \(k-1\) bits of its block
are one and coordinate \(j\) is pivotal for the values of the other
blocks. These two events are independent. Therefore
\begin{equation}
\label{eq:and-block-influence}
I_{1/2}(F)
=k2^{-(k-1)}I_p(f)
=2kpI_p(f)
\le kb.
\end{equation}
By Theorem~\ref{thm:friedgut}, there is a Boolean approximant \(H\)
to \(F\) with error at most \(\alpha\), using at most
\(J_{\mathrm{unif}}(kb,\alpha)\) of the individual bits \(X_{j,a}\).
Let \(J\subseteq S\) be the set of blocks touched by these bits.
Then \(\abs J\le J_{\mathrm{unif}}(kb,\alpha)\).
Reveal all bits in every block indexed by \(J\). Since \(H\) is
measurable with respect to these revealed blocks, the Boolean
predictor with smallest conditional error from the revealed blocks
has total error at most that of \(H\). More explicitly, this
predictor outputs one when the conditional probability of \(F=1\)
is at least \(1/2\), with any fixed convention at equality.
The unrevealed blocks remain independent of the revealed blocks,
and the dependence of \(F\) on a revealed block is only through its
AND value. Consequently
\[
\Pr[\,F=1\mid (X_{j,a})_{j\in J,\,a\in[k]}\,]
=
\Pr[\,f(\{j:Z_j=1\})=1\mid (Z_j)_{j\in J}\,].
\]
The optimal predictor is therefore a Boolean function only of
\((Z_j)_{j\in J}\). Regard it as a function
\(\widetilde f:2^S\to\{0,1\}\) on the original coordinates.
The induced law of the original input is \(\mu_p^S\), so
\[
\Pr_{R\sim\mu_p^S}[\,f(R)\ne\widetilde f(R)\,]\le\alpha.
\]
Thus \(J(p,b,\alpha)=J_{\mathrm{unif}}(kb,\alpha)\) is a valid
choice, increased to one if desired.
\end{proof}
\begin{remark}
The junta approximants need not be monotone. In the reduction, the
original conditioned functions will be monotone, but the argument
uses only their approximation errors and their coordinate supports.
For any fixed finite collection of dyadic biases, the maximum of the
bounds in Corollary~\ref{cor:dyadic-junta} remains independent of the
alphabet size.
\end{remark}
==== END Constant-factor-hardness-of-directed-feedback-vertex-set//preliminaries.tex ====
==== BEGIN Constant-factor-hardness-of-directed-feedback-vertex-set//ranks.tex ====
\section{Rank spreading and the surviving order}
\label{sec:ranks}
The distribution of rank embeddings used in the construction makes comparisons
at different triples of positions nearly indistinguishable. We first prove
this statement, and then show how it turns a surviving topological order into
compatible monotone Boolean functions.
\subsection{A distribution on increasing embeddings}
For a finite set $S$, write $\binom{S}{3}$ for its three-element subsets,
each represented in increasing order when $S$ is ordered. For probability
measures $\mu,\mu'$ on a common finite space $\Omega$, we use the convention
\[
\TV(\mu,\mu')=\max_{\mathcal A\subseteq\Omega}
\abs{\mu(\mathcal A)-\mu'(\mathcal A)}.
\]
\begin{lemma}[Rank spreading]
\label{lem:rank-spreading}
For every integer $L\ge3$ and every $\eta>0$, there are an integer $N\ge L$
and a rational probability distribution on increasing maps
$\psi\colon[L]\hookrightarrow[N]$ such that, for all
$I,I'\in\binom{[L]}{3}$,
\begin{equation}
\label{eq:rank-spreading-tv}
\TV\bigl(\mathcal L(\psi(I)),\mathcal L(\psi(I'))\bigr)\le\eta.
\end{equation}
Here $\mathcal L$ denotes the law of a random variable, and all the laws in
Equation~\eqref{eq:rank-spreading-tv} use the same random map $\psi$.
\end{lemma}
\begin{proof}
Choose a positive number $\delta<\eta/2$. Let
$\mathcal I=\binom{[L]}{3}$. Partition $[0,1]$ into a finite number $b$ of
intervals, each of diameter at most $\delta$, assigning boundary points to one
of their adjacent intervals. The finite Ramsey theorem for triples
\cite[Theorem~B]{Ramsey1930} gives an $N$ such that every coloring of
$\binom{[N]}{3}$ with at most $b^{\abs{\mathcal I}^2}$ colors has a
monochromatic set of size $L$.
Consider the following finite zero-sum game. The minimizing player chooses
an increasing map $\psi\colon[L]\hookrightarrow[N]$. The maximizing player
chooses a triple $(I,I',\mathcal A)$, where $I,I'\in\mathcal I$ and
$\mathcal A\subseteq\binom{[N]}{3}$. The payoff to the maximizing player is
\[
\ind{\psi(I)\in\mathcal A}-\ind{\psi(I')\in\mathcal A}.
\]
Fix an arbitrary mixed strategy $\tau$ of the maximizing player. Let
$w_{I,I'}$ be its marginal probability of the ordered pair $(I,I')$. When
$w_{I,I'}>0$, define, for $Z\in\binom{[N]}{3}$,
\[
q_{I,I'}(Z)=\Pr_{\tau}[Z\in\mathcal A\mid I,I'];
\]
put $q_{I,I'}(Z)=0$ when $w_{I,I'}=0$.
Color $Z$ by the vector of intervals containing $q_{I,I'}(Z)$, one interval
for every ordered pair $(I,I')\in\mathcal I^2$. The number of possible
colors is at most $b^{\abs{\mathcal I}^2}$, so there is a monochromatic
$L$-element set. Let $\psi$ be its increasing enumeration. For every
ordered pair $(I,I')$, both $\psi(I)$ and $\psi(I')$ are triples in this
set, and hence
\[
\abs{q_{I,I'}(\psi(I))-q_{I,I'}(\psi(I'))}\le\delta.
\]
The expected payoff against $\tau$ is consequently at most
\[
\sum_{I,I'\in\mathcal I}w_{I,I'}\,
\bigl(q_{I,I'}(\psi(I))-q_{I,I'}(\psi(I'))\bigr)
\le\delta.
\]
The number $N$ was chosen from a bound on the number of colors that does
not depend on $\tau$. Thus every mixed strategy of the maximizing player
has a pure response with payoff at most $\delta$.
By the finite minimax theorem \cite[Section~II.3]{vonNeumann1928}, there is a probability
distribution $\mu$ on increasing maps for which the expected payoff against
every pure test is at most $\delta$. Choose a rational probability
distribution $\widehat\mu$ on the same finite space with
\[
\sum_{\psi}\abs{\widehat\mu(\psi)-\mu(\psi)}<\eta/2.
\]
Such distributions are dense in the finite probability simplex. Since
each payoff lies in $[-1,1]$, this replacement changes any expected payoff
by less than $\eta/2$. Thus every pure test has expected payoff less than
$\delta+\eta/2<\eta$ under $\widehat\mu$. The ordered pairs include
both $(I,I')$ and $(I',I)$, and $\mathcal A$ ranges over all subsets of
$\binom{[N]}{3}$. The resulting inequalities give
Equation~\eqref{eq:rank-spreading-tv}.
\end{proof}
\subsection{Boolean functions from rank comparisons}
For the remainder of this section and
Sections~\ref{sec:prefix}--\ref{sec:soundness}, suppose that the constructed
weighted digraph has a feedback vertex set $F$ of cost at most $D$.
Fix a total topological order $\prec$ of the surviving vertices. Every
rank vertex survives, since it has weight $D+1$. In particular, the
constant vertices satisfy
\[
o_1\prec o_2\prec\cdots\prec o_N.
\]
All subsequent random data are sampled after $F$ and this order have been
fixed. In a test family of total mass $W$, the deletion cost paid by $F$
in that family is exactly $W$ times the probability that its sampled test
vertex belongs to $F$.
For an allowed tuple $\mathbf d$, a subset $E\subseteq\Lambda_{\mathbf d}$,
and indices $1\le ad$, then
$\lambda\notin E\cup Z$, so the profiles take values $\psi(c+2)$ and
$\psi(L-1)$. Here
\[
c+2=10d+17<10\ell+10
\le10k_{\max}+10=L-20B_0\), set \(J_w=\varnothing\) and choose
\(\widetilde f_{w,i}\) to be the constant-zero function; no error
guarantee is asserted at that vertex.
We suppress the dependence of \(J_w\) on \(\mathcal D\) and \(i\).
This defines one list for every actual game vertex from
\((\mathcal D,i)\) alone. The functions \(f_w\), including the
fallback functions, are already defined for all vertices from
\(\mathcal D\) alone. Thus the choice of a junta or list uses no
information about the fresh sampled edge. It may depend on the
fixed game instance and the fixed topological order, as may any
labeling used in a soundness argument. A repetition in the prefix,
or an endpoint that also occurs in the prefix, does not change this
conditional independence: the fresh edge was drawn independently
of the entire prefix.
By Lemma~\ref{lem:list-decoding}, for every fixed value of
\(\mathcal D\),
\[
\Pr_{e\sim\nu}
[\,\pi_e(J_u)\cap J_v\ne\varnothing
\mid\mathcal D\,]\le\theta J^2.
\]
After averaging over \(\mathcal D\), this remains the bound on the
list-intersection event under the common law.
Also, Proposition~\ref{prop:pivotal-budget} and Markov's
inequality give the averaged bound
\begin{equation}
\label{eq:budget-cutoff}
\Pr[\,B_u>B_0\ \text{or}\ B_v>B_0\,]
\le\frac{\E B_u+\E B_v}{B_0}
\le 2\gamma.
\end{equation}
Here we have used the actual endpoint marginals of \(\nu\).
Equation~\eqref{eq:budget-cutoff} is a bound under the joint law of
\((\mathcal D,e)\); no corresponding pointwise bound conditional
on \(\mathcal D\) is needed.
Let \(\mathcal A_i\) be the event, determined by
\((\mathcal D,e)\), that both budgets are at most \(B_0\) and
\(\pi_e(J_u)\cap J_v=\varnothing\). The preceding bounds imply
\begin{equation}
\label{eq:junta-exceptions}
\Pr[\mathcal A_i^c]\le2\gamma+\theta J^2.
\end{equation}
Fix \((\mathcal D,e)\) in \(\mathcal A_i\).
In the coupled experiment, all bits used by the big-side junta
belong to fibers indexed by \(\pi_e(J_u)\), and all bits used by
the small-side junta belong to fibers indexed by \(J_v\).
These are disjoint collections of independently generated fibers.
Consequently
\(\widetilde f_{u,i}(R_u)\) and
\(\widetilde f_{v,i}(R_v)\) are independent in the coupled
experiment. They are also independent in the independent
experiment, and their marginal distributions are unchanged.
Their joint distributions therefore agree in the two experiments.
This includes the case of a constant junta with an empty
coordinate set.
The conditional approximation error for each endpoint in
Equation~\eqref{eq:junta-error} is at most \(\gamma\) in either
experiment, because both have exactly the stipulated product
marginals. Replacing \(f_u,f_v\) by their respective juntas changes
the conditional probability of the pattern \((1,0)\) by at most
\(2\gamma\), by a union bound. Doing this in both experiments and
using equality of the junta joint distributions yields
\begin{align*}
&\left|
\Pr_{\mathrm{ind},i}[\,f_u(R_u)=1,\ f_v(R_v)=0
\mid\mathcal D,e\,]
\right.\\[-2mm]
&\hspace{22mm}\left.
-\Pr_{\mathrm c,i}[\,f_u(R_u)=1,\ f_v(R_v)=0
\mid\mathcal D,e\,]
\right|\le4\gamma
\end{align*}
on \(\mathcal A_i\).
On its complement the difference is at most one.
Integrating over the unchanged law of \((\mathcal D,e)\), and using
Equation~\eqref{eq:junta-exceptions} and
Lemma~\ref{lem:comparison-charge}, gives
\begin{align}
\label{eq:product-comparison-error}
&\Pr_{\mathrm{ind},i}[\,f_u(R_u)=1,\ f_v(R_v)=0\,]\notag\\
&\qquad\le
2\rho+\frac{M2^T D}{K}
+2\gamma+\theta J^2+4\gamma
\le10\gamma.
\end{align}
The conditional probability of the pattern in the independent
experiment is exactly \(h_u(p_i)(1-h_v(q_i))\).
Finally, \(\gamma=p_M/1000\) and \(p_M\le p_i\), so
\[
10\gamma=\frac{p_M}{100}\le\frac{p_i}{16}.
\]
This proves Equation~\eqref{eq:product-comparison}.
\end{proof}
\subsection{The dyadic tail contradiction}
\begin{proposition}[Weighted soundness]
\label{prop:weighted-soundness}
If the game has value at most \(\theta\), every feedback vertex set
of the constructed weighted digraph has cost strictly greater
than \(D\).
\end{proposition}
\begin{proof}
Suppose that \(F\) has cost at most \(D\), as assumed throughout
this section. Fix \(i\in[M]\), and let
\[
\mathcal H_i=\{h_v(q_i)\ge1/2\}
\]
under the common distribution of \((\mathcal D,e)\).
On its complement,
\(h_u(p_i)\le2h_u(p_i)(1-h_v(q_i))\). Consequently
Propositions~\ref{prop:prefix-lower-bound}
and~\ref{prop:product-comparison} imply
\begin{align*}
\E[\,h_u(p_i)\ind{\mathcal H_i}\,]
&=\E h_u(p_i)
-\E[\,h_u(p_i)\ind{\mathcal H_i^c}\,]\\
&\ge\frac{p_i}{4}
-2\E[\,h_u(p_i)(1-h_v(q_i))\,]\\
&\ge\frac{p_i}{8}.
\end{align*}
Since \(0\le h_u(p_i)\le1\), we obtain
\(\Pr[\mathcal H_i]\ge p_i/8\).
Lemma~\ref{lem:pivotal-inequalities} also gives
\(h_v(q_i)\le q_iB_v=2p_iB_v\) pointwise.
Thus, on \(\mathcal H_i\), one has \(B_v\ge1/(4p_i)\), and hence
\begin{equation}
\label{eq:dyadic-budget-tails}
\Pr\!\left[B_v\ge\frac1{4p_i}\right]\ge\frac{p_i}{8},
\qquad i\in[M].
\end{equation}
These are tail estimates for one random variable \(B_v\) under one
fixed probability law. The definition of \(f_v\), and therefore
that of \(B_v\), does not use the fresh threshold index \(i\).
The junta approximants used to prove the individual estimates may
depend on \(i\), but this does not alter \(B_v\).
Put \(a_i=1/(4p_i)\) for \(i\ge1\), and \(a_0=0\).
For every real \(x\ge0\),
\[
x\ge\sum_{i=1}^{M}(a_i-a_{i-1})\ind{x\ge a_i}.
\]
Indeed, if \(a_j\) is the largest crossed threshold, the sum on the
right telescopes to \(a_j\le x\); if no threshold is crossed, it
is zero. Taking expectations and using
Equation~\eqref{eq:dyadic-budget-tails} yields
\[
\E B_v
\ge\sum_{i=1}^{M}(a_i-a_{i-1})\Pr[B_v\ge a_i]
\ge\sum_{i=1}^{M}\frac{a_i}{2}\frac{p_i}{8}
=\frac M{64}.
\]
Here \(a_i=2a_{i-1}\) for \(i\ge2\), while
\(a_1-a_0=a_1\ge a_1/2\).
Since \(M=128(D+1)\), this gives
\(\E B_v\ge2(D+1)\), contradicting
Proposition~\ref{prop:pivotal-budget}.
No feedback vertex set of cost at most \(D\) can therefore exist.
\end{proof}
==== END Constant-factor-hardness-of-directed-feedback-vertex-set//soundness.tex ====
==== BEGIN Constant-factor-hardness-of-directed-feedback-vertex-set//unweighting.tex ====
\section{Removing the vertex costs}
\label{sec:unweighting}
The weighted gap converts to an unweighted gap without requiring a common
denominator for all vertex costs. Rounding upward at a scale determined
by the number of vertices controls the additive loss. Independent-copy
blowups also occur in earlier DFVS hardness reductions
\cite[Section~2]{GuruswamiLee2016}. The rounding below allows arbitrary
rational costs of polynomial bit length without expanding a common
denominator.
\begin{lemma}[Rounding and cloning]
\label{lem:round-and-clone}
Let $G$ be a loopless digraph on $S\ge1$ vertices with positive rational
vertex costs $w_v\le C$. Set $c_v=\lceil Sw_v\rceil$. Replace every vertex
$v$ by an independent set $\mathcal C_v$ of $c_v$ unweighted vertices, and
replace every arc $u\to v$ by all arcs from $\mathcal C_u$ to
$\mathcal C_v$. Call the resulting digraph $\widehat G$. Then
\begin{equation}
\DFVS(\widehat G)
=\min\left\{\sum_{v\in F}c_v:
F\text{ is a feedback vertex set of }G\right\}.
\label{eq:clone-exact-optimum}
\end{equation}
The number of vertices of $\widehat G$ is at most $CS^2+S$. For fixed
$C$, this is a deterministic polynomial construction in the encoding size
of $G$ and its costs. Moreover:
\begin{enumerate}[label=(\roman*)]
\item a feedback vertex set of $G$ of cost at most $a$ yields a feedback
vertex set of $\widehat G$ of size at most $S(a+1)$;
\item if every feedback vertex set of $G$ has cost greater than $b$,
then $\DFVS(\widehat G)>Sb$.
\end{enumerate}
\end{lemma}
\begin{proof}
Let $F$ be a feedback vertex set of $G$. Deleting every cluster
$\mathcal C_v$ with $v\in F$ leaves only clusters over the acyclic digraph
$G-F$. Lift a topological order of $G-F$ by placing all vertices of each
cluster consecutively. Since clusters are independent, this is a
topological order of the surviving vertices of $\widehat G$. It gives a
feedback vertex set of size $\sum_{v\in F}c_v$.
Conversely, let $Q$ be any feedback vertex set of $\widehat G$, and define
\[
F_Q=\{v\in V(G):\mathcal C_v\subseteq Q\}.
\]
If $G-F_Q$ contained a directed cycle, every cluster over that cycle would
contain a surviving vertex. Choosing one such vertex from each cluster
would lift the original cycle to a directed cycle of $\widehat G-Q$,
because all the intercluster arcs in the requisite directions are present.
This is impossible. Thus $F_Q$ is a feedback vertex set of $G$, and
\[
\sum_{v\in F_Q}c_v\le\abs{Q}.
\]
Together with the preceding construction, this proves
Equation~\eqref{eq:clone-exact-optimum}. In particular, partial deletions
from a cluster cannot improve the optimum beyond the corresponding
choice of completely deleted clusters.
For every $v$ we have
\[
Sw_v\le c_vDS.
\end{array}
\]
This last transformation is polynomial because $C_A$ is fixed. Set
$k=5S$ and output the pair $(\widehat G,k)$. In the YES case,
$\DFVS(\widehat G)\le k$, whereas in the NO case
\[
\DFVS(\widehat G)>DS=10AS>5AS=Ak.
\]
Thus this pair has the promised gap of Theorem~\ref{thm:main}.
A deterministic polynomial-time $A$-approximation would return a feasible
feedback vertex set of size at most $5ASAk.
\end{array}
\]
\end{corollary}
\begin{proof}
Let $G=(V,E)$ be an unweighted loopless digraph, with $n=\abs{V}$ and
$m=\abs{E}$. Split each vertex $v$ into $v^-,v^+$ and insert the arc
$a_v:v^-\to v^+$. For every original arc $e=(u,v)$, introduce $n+1$
fresh private vertices $w_{e,j}$ and the paths
\[
u^+\longrightarrow w_{e,j}\longrightarrow v^-\qquad(1\le j\le n+1).
\]
Call the resulting unweighted digraph $H$. All private vertices are
distinct, so $H$ has no loops or repeated arcs, even if $G$ has opposite
arcs. It has $2n+(n+1)m$ vertices and $n+2(n+1)m$ arcs and is explicitly
constructible in polynomial time.
If $S$ is a feedback vertex set of $G$, deleting the arcs $a_v$ for
$v\in S$ destroys every directed cycle of $H$: a surviving cycle would
alternate distinguished arcs with connector paths and project to a
directed closed walk in $G-S$. Hence
$\operatorname{DFAS}(H)\le\DFVS(G)\le n$.
Conversely, let $F$ be any feedback arc set of $H$. If $\abs{F}\ge n$,
return $S=V$, which is a feedback vertex set of size at most $\abs{F}$.
If $\abs{F}