Prove
Lemma 3 ([Evaluation invariant]). Every global game labeling ℓ gives a…Definition 6 ([Test families]). Add the following families of test vertices to…Proposition
Fix such a labeling ℓ . Delete each wildcard test whose evaluated tuple ℓ( d) lies in its star set, and each comparison test whose edge is not satisfied by ℓ . Denote this deletion set by F_ yes . No rank vertex is deleted. We first bound its cost. In a full-prefix test, conditional on any fixed vertex tuple s , the count # j:i_j=i, ℓ(u_j)∈P_j is binomial with mean μ_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 μ , the exponential Markov inequality gives [Z<μ/2] ≤e^ μ/2 [e^ -Z ] ≤(-(1/2-e^ -1 )μ) ≤(-μ/8). Here the middle inequality follows by writing [e^ -Z ]=(1-a+ae^ -1 )^T≤(-Ta(1-e^ -1 )) when Z has parameters T,a . Applying this bound to each scale and taking a union bound over i∈[M] , the deletion probability for a full-prefix test is at most ∑_ i=1 ^ M (-μ_i/8) ≤M(-(p_MT)/(8M)). After multiplication by the mass H , this is at most one by Equation. In a single-label test, membership of the evaluated tuple in the star set is precisely the event j_0=ℓ(w) . Its probability is 1/m_w , so each of the two families contributes cost one. Comparison tests are deleted with probability at most θ , and hence contribute at most Kθ≤1 by Equation. Thus w(F_ yes )≤1+1+1+1=4. To prove that this deletion set is a feedback vertex set, assign to each rank vertex its evaluation under ℓ , as in Lemma 3 ([Evaluation invariant]). 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 and, 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 π_e(ℓ(u))=ℓ(v) . By Equation, ℓ( s u)∈E_u^r(R_u) ℓ( s v)∈E_v^r(R_v). The possible pairs of rank indices at the start and end of Equation 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_ 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.