Theorem 5 — optimal probing set on an acyclic tournament in FPT time (corrected: vertex index range)
OpenDataValidation.Supplement.theorem_5data-validationp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-algorithmstournaments
There is a uniform encoded algorithm with the following guarantee. Given any valid DVP instance whose graph is an acyclic tournament, with and on every edge, it returns an obtainable edge set satisfying and
Its running time is . Thus the output is an actual maximum-weight feasible probing set, not merely a proof that one exists.
Differences from the source:
- encoding: the FPT running time is informal → absolute constants and bound the Cook–Levin steps by ; reason: fixes a concrete computation model and preserves
- reading: “probing set with maximum weight” is not expanded → an obtainable set within budget whose weight dominates every obtainable set within budget; reason: this is the feasible probing-set notion used in §4 and rules out an arbitrary edge subset
- correction: the proof orders but once quantifies → tournament vertices are indexed by ; reason: the displayed order and all subsequent blocks use the number of vertices
Preamble
import Mathlib import Definitions.Def_DataValidation_Supplement_Algorithms set_option autoImplicit false
Formal statement
namespace DataValidation.Supplement
/-- **Theorem 5** (Tinguely--van der Heijden, *Approximation and Hardness for the Data
Validation Problem*, arXiv:2611.06773, sha256 6595f819..., p.3 (PDF p.4), proof pp.10--11
(PDF pp.11--12)). On every deterministic acyclic tournament with positive probing costs, a uniform
encoded algorithm returns an obtainable probing set within budget whose weight is maximum among
all such sets. Its running time is `2^{O(T log T)} n^{O(1)}`.
**Formalization Note.** `IsTournament`, together with validity, is exactly a total-order DAG.
The output is a feasible probing set, not merely a witness that an optimum exists. The constants
`C,d` are absolute and precede the instance. `log` is base two; `T+1` and `n+1` totalize the bound
at small inputs without changing its asymptotic class. The paper's stray `i,j ∈ [m]` is read as
`i,j ∈ [n]`, matching its displayed vertex order. -/
theorem theorem_5 :
∃ (A : SetAlgorithm) (C : ℝ) (d : ℕ), 0 < C ∧
∀ I, I.IsValid → 0 < I.T → IsTournament I →
(∀ e ∈ I.E, I.p e = 1 ∧ 0 < I.τ e) →
FeasibleSet I (A.run I) ∧
(∀ R : Finset I.Edge, FeasibleSet I R →
setWeight I R ≤ setWeight I (A.run I)) ∧
A.time I ≤ Nat.ceil
(C * (2 : ℝ) ^ (C * I.T * Real.logb 2 (I.T + 1)) * (I.n + 1) ^ d) := by sorry
end DataValidation.Supplement
Source
Tinguely, van der Heijden, Approximation and Hardness for the Data Validation Problem, arXiv:2611.06773 (sha256 6595f819…), Theorem 5, p.3 and §4, pp.10–11 (PDF pp.4, 11–12)