Constant-factor hardness of directed feedback vertex set

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

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

By Theorem 2.2, 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

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

Thus J(p,b,\alpha)=J_{\mathrm{unif}}(kb,\alpha) is a valid choice, increased to one if desired.□

Proof. For every generating identification in Equation (3.6),

Thus evaluation is constant on each equivalence class. This remains true when vertices repeat in a tuple: their repeated coordinates are evaluated at the same global label. A rank arc is strictly increasing at every tuple of labels, and hence at the particular tuple supplied by \ell. Its two endpoints cannot become the same equivalence class. Finally, constant profiles all identify with their representatives at the empty tuple, and their evaluated values are the distinct integers 1,\ldots,N.□

Proof. Fix such a labeling \ell. Delete each wildcard test whose evaluated tuple \ell(\mathbf d) lies in its star set, and each comparison test whose edge is not satisfied by \ell. Denote this deletion set by F_{\mathrm{yes}}. No rank vertex is deleted.

We first bound its cost. In a full-prefix test, conditional on any fixed vertex tuple \mathbf s, the count

is binomial with mean \mu_i=p_iT/M. Indeed, indices and subsets are independent between slots, so every slot contributes an independent Bernoulli variable of parameter p_i/M. This argument also applies when the same game vertex appears in several slots. For a binomial random variable Z of mean \mu, the exponential Markov inequality gives

Here the middle inequality follows by writing \E[e^{-Z}]=(1-a+ae^{-1})^T\le\exp(-Ta(1-e^{-1})) when Z has parameters T,a. Applying this bound to each scale and taking a union bound over i\in[M], the deletion probability for a full-prefix test is at most

After multiplication by the mass H, this is at most one by Equation (3.1). In a single-label test, membership of the evaluated tuple in the star set is precisely the event j_0=\ell(w). Its probability is 1/m_w, so each of the two families contributes cost one. Comparison tests are deleted with probability at most \theta, and hence contribute at most K\theta\le1 by Equation (3.3). Thus

To prove that this deletion set is a feedback vertex set, assign to each rank vertex its evaluation under \ell, as in Lemma 3.2. Every rank arc strictly increases the assigned value. For a retained wildcard vertex, let C_r be the cell containing its evaluated tuple and assign the test value z_r. The evaluated tuple is outside the star set. Thus Equations (3.7) and (3.8), at that tuple, put every incoming rank value strictly below z_r and every outgoing rank value strictly above it.

For a retained comparison, the evaluated prefix is the same on both sides and \pi_e(\ell(u))=\ell(v). By Equation (3.11),

The possible pairs of rank indices at the start and end of Equation (3.13) are therefore (2,3), (2,18), and (17,18). Each is increasing, so the corresponding evaluated values are strictly increasing as well. Assign this test any real value strictly between its two endpoint values.

These assignments coexist because there are no arcs between test vertices. Every arc remaining after deletion of F_{\mathrm{yes}} strictly increases the assigned real value. A directed cycle would force a strict increase back to its starting value, which is impossible. Thus the remaining digraph is acyclic.□

Proof. Put n=1+\abs{U}+\abs{V}+\abs{E}, counting parallel constraints as distinct edges if necessary. The number of allowed tuples is at most (2T+1)n^T. By Equation (3.5), a tuple has at most N^{m^T} formal rank vertices. Both factors other than n^T are constants for fixed A.

For each slot, there are at most M2^m choices of index and subset. The support of the rank law, the number of permutations of either alphabet, and all choices of individual labels are also bounded by constants. A full-prefix test uses T game-vertex slots, so this family has O_A(n^T) outcomes. A single-label test has at most T-1 prefix vertices and one endpoint, again giving O_A(n^T) outcomes. A comparison test has at most T-1 prefix vertices and one input edge; its remaining choices, including the coupled subsets and candidate cell, range over constant finite sets. Thus there are O_A(n^T) comparison outcomes as well. Here O_A allows the implicit constant to depend on A.

Within a tuple there are at most N^{2m^T} formal rank arcs, and a wildcard vertex has at most 2N^{m^T} incident arcs. Comparisons have two arcs each. Therefore the total numbers of formal vertices and arcs are O_A(n^T). Computing the equivalence relation in Equation (3.6) and discarding duplicate arcs cannot increase these counts. Lemma 3.2 rules out rank self-loops, and every other arc joins a rank vertex to a distinct test vertex.

It remains to account for numerical representation. Marginal endpoint probabilities are sums of input rational edge probabilities. They can be computed with polynomial bit length: a common denominator can be formed from the product of the input denominators, whose bit length is at most their total encoding length. Every outcome probability is a product of at most T+1 input-dependent edge or endpoint probabilities and a fixed number of rational factors depending only on A. Its bit length is therefore polynomial in the input encoding length. Zero-probability outcomes are omitted. The rank law supplied by Lemma 4.1 is a fixed finite rational table and may be hardwired into the reduction for this fixed A. Alternatively, a computable finite Ramsey bound and exhaustive search over finite rational probability tables recover such a law: each total-variation constraint is an exact rational inequality, and the strict slack in the proof of Lemma 4.1 ensures that the search terminates. This preprocessing depends only on A, not on the input game.

Finally, each outcome probability is at most one. Every test cost is therefore at most its family’s total mass, while every rank cost is D+1. All costs are bounded by

which depends only on A. These estimates establish both the claimed running time and the cost bound. No efficient dependence on a variable parameter A is asserted.□

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 [11, Theorem B] 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

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},

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

The expected payoff against \tau is consequently at most

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 [14, Section II.3], 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

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 (4.1).□

Proof. Fix \mathbf d and E\subseteq\Lambda_{\mathbf d}. For integers r_1<r_2<r_3 in [N], let x_{r_1,r_3} be the profile taking value r_1 on E and r_3 on its complement. Once the surviving order is fixed, the function

is a deterministic Boolean function of this triple alone. Applying Lemma 4.1 to it shows that

for any two increasing triples of positions, whether usable or not.

Equation (4.5) compares expectations; it does not by itself control disagreement under the same embedding. We obtain that control through pointwise ordered pairs of bits, for which the probability of disagreement equals the absolute difference of expectations. Fix a usable triple (a,c,h) and abbreviate

The bits A_0 and A_1 compare the same rank vertex to two constant vertices. They are pointwise ordered: A_0\le A_1 if c\ge15, and A_1\le A_0 if c\le15. Equation (4.5) therefore gives \Pr[A_0\ne A_1]\le\eta.

The profile of b_{\mathbf d}^{\psi}(E;1,c+1) is strictly smaller at every coordinate than the profile of b_{\mathbf d}^{\psi}(E;2,L-1): on E use 1<2, and on its complement use c+1<L-1. The strict rank arc from the former vertex to the latter forces A_2\ge A_1. Similarly, 1<a and c+1<h imply A_2\ge A_3. Applying Equation (4.5) to these ordered pairs gives

A union bound yields

There are at most L^3 usable triples and 2^{\abs{\Lambda_{\mathbf d}}} subsets E. A second union bound proves the first inequality of Equation (4.4). Every allowed tuple has length at most T and each slot alphabet has size at most m, so \abs{\Lambda_{\mathbf d}}\le m^T. The choice 3\eta L^3 2^{m^T}\le\rho proves the second inequality. Finally, averaging the pointwise bound over any tuple distribution independent of \psi gives the last assertion.□

Proof. For E\subseteq E', compare

The first profile is strictly smaller everywhere: the index pairs in E, E'\setminus E, and \Lambda_{\mathbf d}\setminus E' are, respectively, (2,3), (2,18), and (17,18). The rank arc consequently implies

Both triples are usable, so goodness identifies these two bits with g_{\mathbf d}(E') and g_{\mathbf d}(E). For the extreme sets, the reference profile is o_{\psi(L-1)} when E=\varnothing and o_{\psi(2)} when E=\Lambda_{\mathbf d}. Their positions relative to o_{\psi(15)} give the claimed values.□

Proof. The profile on \Lambda_{\mathbf s w} that takes value \psi(a) on E\times\Lambda_w and \psi(h) elsewhere is the pullback of the corresponding profile on \Lambda_{\mathbf s} under the projection dropping the last slot. Definition 3.1 identifies the two rank vertices. Their comparisons to the same constant marker are identical, proving Equation (4.6). Apply this identity both to the reference triple and to every usable triple: goodness of the extension gives goodness of the shorter tuple for each subset E. Iteration proves the final assertion. The projection identity holds on the formal product alphabets even when a game vertex occurs in more than one slot.□

Proof. Set c=10d+15 and define the rank vertices

We first check the wildcard’s incident arcs. If \lambda\in C_\ell\setminus Z with \ell\le d, then \lambda\in E, so the two profiles take values \psi(2) and \psi(c-2), respectively. The inequalities

place these values strictly below and strictly above z_\ell=\psi(10\ell+10). If instead \ell>d, then \lambda\notin E\cup Z, so the profiles take values \psi(c+2) and \psi(L-1). Here

which gives the required strict inequalities again. Thus the constructed digraph contains the arcs

Empty cells impose no conditions in these checks. The first case is absent when d=0, and the second is absent when d=k.

Since 0\le d\le k\le k_{\max} and L=10k_{\max}+30,

Both (2,c,c+2) and (c-2,c,L-1) are therefore usable triples. Goodness and Equation (4.7) show that v^- does not precede o_{\psi(c)}, whereas v^+ does precede it. If v_{\mathrm{test}} survived, the displayed path would give v^-\prec v_{\mathrm{test}}\prec v^+\prec o_{\psi(c)}, a contradiction. Hence v_{\mathrm{test}}\in F.□

Proof. Goodness is inherited by all the prefixes. A cumulative union of cells at depth j, lifted to the full product alphabet, is a cumulative union at a boundary of the depth-T partition. This follows from the lexicographic ordering: all refinements of an earlier cell precede all refinements of a later cell. By Lemma 4.5, the cumulative-set bit at that lifted boundary is its bit at depth j. In particular, the two boundaries on either side of C^{(j)}_{\tau_j} have bits 0 and 1. Monotonicity places the full transition between these boundaries, which proves the asserted containment. Its nonemptiness follows because an empty cell cannot change a cumulative-set bit.

At step j, the depth-(j-1) transition cell has two children: its membership-1 child first, followed by its membership-0 child. The cumulative union at the boundary between these children is exactly

The bit of this set under g_{\mathbf s_j} is f_{u_j,\mathcal D_{j-1}}(P_j). Here the extension \mathbf s_{j-1}u_j=\mathbf s_j is good, so the fallback rule is not used. The bit before both children is 0 and the bit after both is 1. The transition is therefore in the first child if and only if the intermediate bit is 1. If either child is empty, the same statement follows from equality of its two boundary sets. The full transition refines the selected child, giving Equation (5.4).□

Proof. Consider the full-prefix experiment in Definition 3.5, with data of length T and an independent embedding. Denote its probability and expectation by \Pr_{\mathrm{full}} and \E_{\mathrm{full}}. Let Z_T be the star set of its wildcard test vertex, and let \mathcal A be the event that \mathbf s_T is good and its transition cell is not starred.

The star predicate is constant on each full cell: all label tuples in that cell have the same membership vector, and hence the same counts at each scale. Suppose that \mathbf s_T is good and its transition cell is starred. At the cut immediately before that cell, put

This is precisely the union of the nonstar portions of the cells before the cut. It is contained in C^{(T)}_{<\tau_T}, whose bit is 0. Moreover, E\cup Z_T contains C^{(T)}_{\le\tau_T}, whose bit is 1: adjoining the stars restores every earlier starred cell and includes the entire starred transition cell. Monotonicity gives

Lemma 4.6 forces deletion of this test vertex.

The full-prefix family has total mass H, so its deletion probability is at most D/H. The full tuple is independent of the embedding, and Lemma 4.3 bounds its badness probability by \rho. We conclude that

The last inequality follows from the parameter choices: \rho\le\gamma\le1/4000 and D/H<1/8.

Define \mathcal D_{j-1} from this experiment as in Lemma 5.2. For a fixed i\in[M], set

On \mathcal A, the transition cell is nonstarred, so the definition of Z_T and Equation (5.4) give Y_i\ge p_iT/(2M). On all other outcomes, Y_i\ge0, including outcomes for which some conditioned functions use the fallback rule. It follows from Equation (5.6) that

We now calculate this expectation without conditioning on \mathcal A. For each j, condition on the embedding, the first j-1 prefix slots with all their data, and the new vertex u_j. The function f_{u_j,\mathcal D_{j-1}} is determined by these choices: both the goodness test for \mathbf s_j and any fallback choice are independent of the fresh i_j and P_j. Since i_j is uniform in [M] and P_j has law \mu_{p_i}^X conditional on i_j=i,

The marginal law of the conditioning data and u_j is the common law of (\mathcal D,u) conditional on t=j-1. Indeed, the new vertex has law \nu_U independently of the earlier slots, just as does the big endpoint of the independently sampled edge. Therefore

Together with Equation (5.7), this proves Equation (5.5).□

Proof. Give each j\in S an independent uniform arrival time T_j\in[0,1]. With probability one all these times are distinct. For each j, let \sigma_j be the order in which the other elements arrive, and let \mathcal A_j be the event that some prefix of \sigma_j witnesses j’s pivotality in Definition 6.1. The permutation \sigma_j is uniform, so

Moreover, \mathcal A_j is determined entirely by the arrival times of elements other than j, and hence is independent of T_j.

For the influence inequality, put

This set has law \mu_p^{S\setminus\{j\}} and is a prefix of \sigma_j. By monotonicity, the event defining I_{p,j}(f) is exactly

which is contained in \mathcal A_j. Summing I_{p,j}(f)\le\Pr(\mathcal A_j) over j proves I_p(f)\le B(f).

For the acceptance inequality, put R(p)=\{j\in S:T_j\le p\}, which has law \mu_p^S. Along the complete arrival sequence, the value of f starts at zero, ends at one, and never decreases. There is therefore a unique arriving element at which it changes from zero to one. If f(R(p))=1 and this element is j, then T_j\le p, and the elements arriving before j form a prefix of \sigma_j witnessing \mathcal A_j. Consequently, up to the null event of tied arrival times,

A union bound and the independence established above give

Only the possible-witness event \mathcal A_j is asserted to be independent of T_j; no independence of the actual switching element is needed.□

Proof. Fix either side of the game and sample w independently of \mathcal D from that side’s endpoint marginal. Its alphabet size m_w is constant on the chosen side. This is exactly the marginal law of the shared data and endpoint in the corresponding single-label test family of Definition 3.5.

First fix \mathcal D,w for which the extension \mathbf s w is good. The conditioned function f_w then uses the transition cell C_{r_*}. The remaining randomness of a single-label test consists of a uniform label j_0\in\Lambda_w and an independent uniform permutation \sigma of \Lambda_w. Its star set is

and its ordered cells are C_\ell\times\{j\}, first ordered by \ell and then by \sigma. Suppose some prefix R of \sigma with j_0 omitted satisfies

Choose a cut among the refined cells belonging to C_{r_*}, including either boundary of this block if necessary, so that precisely the nonstar labels in R have been passed within that block. Such a cut exists because deleting j_0 from the sequence \sigma preserves the order of every other label. For R=\varnothing one may cut before the block, and for R=\Lambda_w\setminus\{j_0\} one may cut after the block. Let E be the union of all refined cells before the cut, with all stars removed. Then exactly

In particular,

The second inclusion restores the stars in all earlier prefix cells; the additional stars in later cells only enlarge the set. Monotonicity of g_{\mathbf s w} and the definition of f_w now imply

Lemma 4.6 therefore forces this test vertex to belong to F.

This argument uses the ordered partition with its empty cells retained; the set identities remain valid when some of those cells are empty. They also hold on the formal product label domain when w or another game vertex occurs repeatedly in the tuple. No independence of labels in repeated slots is assumed, and the use of f_w rests only on the prefix identifications of Lemma 4.5.

For each fixed j_0, deleting j_0 from a uniform permutation of \Lambda_w gives a uniform permutation of \Lambda_w\setminus\{j_0\}. Averaging the forced-deletion event over the uniform choice of j_0 therefore gives, whenever \mathbf s w is good,

Here a test is charged once if a witnessing prefix exists, regardless of how many prefixes witness the same label’s pivotality.

Let \mathcal G_w denote the event that \mathbf s w is good. The total mass of the chosen test family is m_w, and its vertices carry their sampling probabilities times this mass. Thus, on taking expectations, the cost spent by F in this family is at least \mathbb E[B_w\mathbf 1_{\mathcal G_w}]. Since the total cost of F is at most D,

On the complementary event the fallback function is still monotone, with bottom zero and top one, so Definition 6.1 gives B_w\le m_w. The sampled-extension bound from Equation (5.3) gives \Pr(\mathcal G_w^c)\le\rho; equivalently, one may apply Lemma 4.3 after fixing the sampled vertex tuple, which is independent of \psi. As m_w\le m and \rho\le1/m,

Adding the two bounds proves \mathbb E B_w\le D+1 for either endpoint marginal, and hence proves Equation (6.1).□

Proof. Let \mathcal G be the event that both extended tuples \mathbf s u and \mathbf s v are good. The tuple choices are independent of \psi, so Lemma 4.3, averaged over these choices, gives \Pr[\mathcal G^c]\le2\rho. On \mathcal G, both conditioned functions use the same prefix transition index r_*, by Definition 5.1 and Lemma 4.5.

Suppose that \mathcal G holds and that f_u(R_u)=1,\ f_v(R_v)=0. Add the candidate-cell draw from the comparison test and consider the outcome r=r_*. The start and end rank vertices of Equation (3.13) are then

The triples (2,15,17) and (3,15,18) are usable. Goodness and the two function values show that the start does not precede o_{\psi(15)}, whereas the end precedes o_{\psi(15)}. If the test vertex were retained, its two arcs would require the start to precede the test vertex and the test vertex to precede the end. This contradicts the fixed topological order. Hence that comparison vertex belongs to F.

For fixed (\mathcal D,e,R_u,R_v) as above, the candidate-cell draw hits r_* with probability 2^{-t}\ge2^{-T}. Let \delta_i be the probability that a comparison vertex is deleted when its fresh threshold index is fixed to i, including the candidate-cell draw. We have proved

In the actual comparison family the threshold index is uniform on [M]. Its deleted weight is

so \delta_i\le MD/K. Combining these inequalities and then adding \Pr[\mathcal G^c]\le2\rho proves Equation (7.1).□

Proof. Independently for each vertex with a nonempty list, choose its label uniformly from that list. Give every empty-list vertex any fixed label from its alphabet. If \pi_e(J_u)\cap J_v\ne\varnothing, there is at least one pair (x,y)\in J_u\times J_v with \pi_e(x)=y. Since u and v are different vertices, the probability of choosing that pair is

The expected value of this random labeling is therefore at least the displayed intersection probability divided by J^2. Every deterministic labeling in its support has value at most \theta, so the expected value is at most \theta. This proves the claim. For the conditional assertion, fix the conditioning data first and repeat the same argument; independence leaves the fresh edge law equal to \nu.□

Proof. Fix i. For each value of \mathcal D, construct a junta approximant for each game vertex, before drawing the fresh edge. For notation, put

If B_w\le B_0, Lemma 6.2 gives I_{\beta_{w,i}}(f_w)\le B_0. Corollary 2.3 and the choice of J in Section 3.1 therefore provide a Boolean function \widetilde f_{w,i} on a coordinate set J_w\subseteq\Lambda_w, with

Choose one such pair by a fixed ordering of the finitely many possible coordinate sets and Boolean truth tables. If B_w>B_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 7.2, for every fixed value of \mathcal D,

After averaging over \mathcal D, this remains the bound on the list-intersection event under the common law. Also, Proposition 6.3 and Markov’s inequality give the averaged bound

Here we have used the actual endpoint marginals of \nu. Equation (7.4) 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

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 (7.3) 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

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 (7.5) and Lemma 7.1, gives

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

This proves Equation (7.2).□

Proof. Suppose that F has cost at most D, as assumed throughout this section. Fix i\in[M], and let

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 5.3 and 7.3 imply

Since 0\le h_u(p_i)\le1, we obtain \Pr[\mathcal H_i]\ge p_i/8. Lemma 6.2 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

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,

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 (7.7) yields

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 6.3. No feedback vertex set of cost at most D can therefore exist.□

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

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

Together with the preceding construction, this proves Equation (8.1). In particular, partial deletions from a cluster cannot improve the optimum beyond the corresponding choice of completely deleted clusters.

For every v we have

Summing over any feedback vertex set F gives

This proves both gap implications by Equation (8.1). Equivalently, the rounded costs c_v/S increase the cost of any deletion set by at most one.

Finally,

There are at most the square of this number of arcs. Each c_v is computed exactly by integer arithmetic on the rational input cost. For fixed C, the vertices and arcs can therefore be listed in polynomial time. Positivity of the costs ensures that every cluster is nonempty before deletions. The assumption that G is loopless ensures that independent clusters realize precisely the prescribed construction.□

Proof of Theorem 1.1. It suffices to prove the claim for every fixed integer A\ge1: given any fixed real factor, choose an integer at least as large. For this integer A, choose the parameters of Section 3.1 and start from the NP-hard promise problem of Theorem 2.1 at the resulting fixed \theta.

By Proposition 3.7, the weighted reduction is deterministic and polynomial in the game input size, and all its costs are bounded by the constant C_A. Proposition 3.6 gives a feedback vertex set of cost at most 4 in the YES case, while Proposition 7.4 shows that every feedback vertex set has cost greater than D=10A in the NO case. Let S be the number of weighted vertices. Lemma 8.1 gives an unweighted digraph \widehat G with the gap

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

Thus this pair has the promised gap of Theorem 1.1.

A deterministic polynomial-time A-approximation would return a feasible feedback vertex set of size at most 5AS<DS on every YES instance. On a NO instance, every feasible feedback vertex set has size greater than DS. Comparing the returned size with the known threshold DS would therefore distinguish the NP-hard promise cases in polynomial time. This proves the asserted NP-hardness for every fixed constant factor, and its deterministic consequence under \mathrm P\ne\mathrm{NP}.□

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

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}<n, return S=\{v:a_v\in F\}, again of size at most \abs{F}. Were there a directed cycle in G-S, every distinguished arc needed to lift it would survive. For each original arc of the cycle, its n+1 connector paths are pairwise edge-disjoint, so at least one survives deletion of F. Choosing these paths would lift the cycle to H-F, a contradiction. Thus the returned S is always a feedback vertex set, and this recovery is polynomial time.

The two maps give \operatorname{DFAS}(H)=\DFVS(G). They also preserve approximation solutions: an A-approximate F yields \abs{S}\le\abs{F}\le A\operatorname{DFAS}(H)=A\DFVS(G). Composing this construction with Theorem 1.1 and retaining its positive integer threshold k proves the stated gap.□