arXiv preprint ·
Approximation and Hardness for the Data Validation Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Finnah, Gönsch and Otto [Eur. J. Oper. Res. 2025] recently introduced the Data Validation Problem (DVP): Given a transitive directed acyclic graph $G$ on $n$ vertices (resp. tasks) and $m$ edges (resp. precedences) and a probing budget, a policy can successively pay a probing fee and probe an edge in $G$ as long as the total probing fees do not exceed the budget. If a probe succeeds, the targeted edge $e$ is removed from $G$ and we receive a reward; if the probe fails, the edge stays in $G$ and cannot be probed again. We seek a policy with maximum expected cumulative reward. Crucially, $G$ must stay transitive throughout the probing process, so a policy can only challenge the precedence between consecutive tasks, that is, only probe edges in the transitive reduction of the current precedence graph. We show that DVP is strongly NP-hard and W[1]-hard with the probing budget $T$ as a parameter, even in the deterministic case (when every probe has probability $0$ or $1$ to succeed) and with unit probing costs and rewards. For the same setting, we give an approximation-preserving reduction from the Densest $k$-Subgraph (D$k$S) Problem, with the consequence that there is no polynomial-time $2^{(\log n)^{1-δ}}$-approximation algorithm and no FPT $\sqrt{T}$-approximation algorithm for DVP, assuming the Almost-Exponential Time Hypothesis and the Strongish Planted Clique Hypothesis, respectively. We also present the first known policies with provable worst-case guarantees for DVP, namely an $m$-approximation algorithm for instances with uniform probabilities and probing costs, a $2T/p_{\min}^T$-approximation algorithm for general instances, where $p_{\min}$ is the minimum probing success probability, and an exact FPT algorithm on tournament graphs, in the deterministic setting.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Quadratic-Time Barriers from Self-Referential SAT
Sublinear Metric Distortion for Matching
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Near linear mixing of random-cluster Glauber dynamics on random regular graphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.