betaFeedback

WorksComputer Science

Approximation and Hardness for the Data Validation Problem

Abstract

Finnah, Gönsch and Otto [Eur. J. Oper. Res. 2025] recently introduced the Data Validation Problem (DVP): Given a transitive directed acyclic graph GG on nn vertices (resp. tasks) and mm edges (resp. precedences) and a probing budget, a policy can successively pay a probing fee and probe an edge in GG as long as the total probing fees do not exceed the budget. If a probe succeeds, the targeted edge ee is removed from GG and we receive a reward; if the probe fails, the edge stays in GG and cannot be probed again. We seek a policy with maximum expected cumulative reward. Crucially, GG 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 TT as a parameter, even in the deterministic case (when every probe has probability 00 or 11 to succeed) and with unit probing costs and rewards. For the same setting, we give an approximation-preserving reduction from the Densest kk-Subgraph (DkkS) Problem, with the consequence that there is no polynomial-time 2(log⁡n)1−δ2^{(\log n)^{1-δ}}-approximation algorithm and no FPT T\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 mm-approximation algorithm for instances with uniform probabilities and probing costs, a 2T/pmin⁡T2T/p_{\min}^T-approximation algorithm for general instances, where pmin⁡p_{\min} is the minimum probing success probability, and an exact FPT algorithm on tournament graphs, in the deterministic setting.

Introduction

Scheduling under precedence constraints is a classic topic in theoretical computer science and operations research. In a precedence-constrained scheduling instance, a set of tasks is given together with a partial order ≺\prec, which is the set of precedence constraints. The partial order can also be encoded as a so-called precedence graph. Given two tasks t,t′t,t', whenever t≺t′t \prec t', task tt must be completed before task t′t' can start. Tasks that are incomparable in the partial order ≺\prec may be processed in any order. The focus of the literature for scheduling with precedence constraints has considered the partial order as an input and has been primarily focused on scheduling tasks according to some objective function depending on when tasks are assigned on a time line. Many variations of precedence constraints have been studied, where the structure of the partial order ≺\prec can strongly affect both the computational complexity of the problem and the optimal objective value [PBM18]. A more basic question has received much less attention: how is the precedence structure obtained in the first place? In practice, the precedence constraints are rarely given explicitly with full confidence and must first be determined. This is a question that has been considered in the operations research community as the Data Validation Problem (DVP) introduced by Finnah, Gönsch and Otto [7]. However, to the best of our knowledge, the computational complexity or approximation bounds for this problem have not been studied from a theoretical perspective. In this paper, we initiate the theoretical study of the problem of determining the precedence structure of a scheduling problem. We give complexity results and approximation guarantees for this problem and several natural variants.

We formally describe DVP following the definition in [7]. We are given a probing budget T∈NT \in\mathbb{N} and a directed acyclic graph (DAG) G=(V,E)G=(V,E) which is also transitive, that is, (u,v)∈E(u,v) \in E and (v,w)∈E(v,w) \in E imply (u,w)∈E(u,w) \in E. Let n:=∣V∣n := |V| and m:=∣E∣m := |E|. Each edge e∈Ee \in E has a weight we∈N0w_e \in\mathbb{N}_0, a probing cost τe∈N0\tau_e \in\mathbb{N}_0, and a success probability pe∈[0,1]p_e \in[0,1], to which is tied a random variable Ωe∼Bernoulli⁡(pe)\Omega_e \sim\operatorname{Bernoulli}(p_e). We assume the random variables {Ωe}e∈E\{\Omega_e\}_{e\in E} to be (mutually) independent.

Iteratively, an (adaptive) probing policy can probe an edge e∈Ee \in E by paying τe\tau_e, i.e., by decreasing the probing budget by τe\tau_e. Then, we reveal the outcome of Ωe\Omega_e (which is unknown before the probe). If the probe succeeds, i.e., in the event that Ωe=1\Omega_e=1, we collect wew_e as a reward, and ee is removed from EE; otherwise, if the probe fails, i.e., if Ωe=0\Omega_e=0, we collect no reward, ee stays in EE and cannot be probed anymore. Crucially, we impose that an edge can only be probed if it lies in the transitive reduction of EE, which is the set of all edges (u,v)∈E(u,v) \in E such that E∖{(u,v)}E\setminus\{(u,v)\} contains no (directed) uu-vv-path,1 which we denote by R(E)\mathcal{R}(E). The transitive reduction of GG can be computed in time O(n2.4)O(n^{2.4}) [1, 3] statically and be updated in time O(n1.528+m)O(n^{1.528}+m) at each edge deletion [10]. The policy must halt if every edge in R(E)\mathcal{R}(E) has already been probed or if τe>T\tau_e>T for any unprobed edge e∈R(E)e \in\mathcal{R}(E). Thereby, a policy π\pi yields the expected total reward W(π):=E[∑e∈E1{π successfully probes e}]W(\pi):=\mathbb{E}\left[\sum_{e\in E}\mathbf{1}_{\{\pi\ \text{successfully probes }e\}}\right], where 1C\mathbf{1}_C denotes the indicator function of an event CC; the goal is to find a policy π∗\pi^* with maximum expected reward, i.e., π∗∈arg⁡max⁡policy πW(π)\pi^* \in\arg\max_{\text{policy }\pi} W(\pi).

We remark that we allow policies to sample random variables other than {Ωe}e∈E\{\Omega_e\}_{e\in E} but that we are independent of {Ωe}e∈E\{\Omega_e\}_{e\in E}. For any E′⊆EE' \subseteq E, we write τ(E′):=∑e∈E′τe\tau(E') := \sum_{e\in E'} \tau_e, w(E′):=∑e∈E′wew(E') := \sum_{e\in E'} w_e and p(E′):=∏e∈E′pep(E') := \prod_{e\in E'}p_e.

Intuitively, the assumption of only probing edges in the transitive reduction is motivated by the interpretation of GG as a precedence graph. If a precedence graph GG contains a path P=(u1,u2,…,uk)P=(u_1,u_2,\ldots,u_k), by transitivity, it also contains the edge e=(u1,uk)e=(u_1,u_k), so removing ee but no edge in PP cancels transitivity, meaning that this framework no longer models the removal of redundant precedences in a meaningful way.

Determining the precedence constraints between tasks is a problem that is often faced in practice. The problem arises in many industries with business processes subject to hard constraints such as precedence constraints, including product design, assembly and manufacturing, project scheduling, construction, and logistics [7, 22]. In such processes, the relation between every pair of tasks is rarely documented explicitly and an expert must be consulted to determine it. Moreover, Otto and Otto [17] showed that probing direct precedence relations can increase the probability of being able to remove the edge in automotive assembly processes. Wang et al. [22] investigated the Assembly Sequence Problem, a problem similar to DVP, which is a well-studied problem in the operations research community. Finnah et al. [7] recently expanded on the model by imposing constraints on the available expert time or cost. They showed that solving the problem, even approximately, can significantly improve business outcomes. Other questions regarding the complexity or approximation guarantees remained open.

Our results

We significantly strengthen the hardness result in [7]. Via an FPT reduction from the kk-Clique problem, we show that DVP is strongly NP-hard and W[1]-hard, even in the deterministic setting (when all probabilities are either 0 or 1) and with unit costs and weights.

Theorem 1. DVP is strongly NP-hard and W[1]-hard when parametrized in TT, even if τe=pe=1\tau_e = p_e = 1 and we∈{0,1}w_e \in\{0,1\} for every edge e∈Ee \in E.

We also achieve an approximation-preserving reduction to the Densest kk-Subgraph Problem (DkS). Thereby, using known (parametrized) inapproximability results for DkS, we achieve strong bounds for DVP as well. The bounds assume the Almost-Exponential Time Hypothesis (Almost-ETH) [13] (a slightly weaker assumption than the Exponential Time Hypothesis) and the Strongish Planted Clique Hypothesis (SPCH) [14], respectively.

Theorem 2. If there is an α\alpha-approximation for DVP (α\alpha can depend on TT, mm or nn), even restricted to the special case that τe=pe=1\tau_e = p_e = 1 and we∈{0,1}w_e \in\{0,1\} for every edge e∈Ee \in E, there is an α⋅(4+O(1/k))\alpha\cdot(4+O(1/k))-approximation for DkS (with T=Θ(opt⁡)T = \Theta(\operatorname{opt}), where opt is the optimum of the DkS instance). As a consequence, even in this special case,

(1) assuming the Almost-ETH, for every δ>0\delta> 0 there is no polynomial-time 2(log⁡n)1−δ2^{(\log n)^{1-\delta}}-approximation algorithm for DVP;

(2) assuming the SPCH, there is no o(T)o(\sqrt{T})-approximation algorithm for DVP in time g(T)⋅nO(1)g(T) \cdot n^{O(1)} for any function gg.

As pointed out in [7], a greedy policy that only considers the currently probable edges, e.g., that always picks as a next probe the best cost-per-value edge arg⁡max⁡e∈R(E)weτe\arg\max_{e \in R(E)} \frac{w_e}{\tau_e}, performs arbitrarily badly, even for very simple instances.

In contrast, we present an adaptive policy which is an mm-approximation in the case of uniform costs and success probabilities and arbitrary weights and arbitrary DAGs.

Theorem 3. For any fixed p∈(0,1]p \in(0,1], there exists an mm-approximation algorithm for DVP with running time O(mn⋅min⁡{m,T})O(mn \cdot\min\{m,T\}) in the case τe=1\tau_e = 1, pe=pp_e = p for every e∈Ee \in E.

We also present a more general policy for arbitrary instances of DVP with an approximation factor that depends on the budget TT and the minimum non-zero success probability.

Theorem 4. There exists an 2Tpmin⁡T\frac{2T}{p_{\min}^T}-approximation algorithm for DVP with running time O(m2n)O(m^2n), where pmin⁡=min⁡{pe:e∈E, pe≠0}p_{\min} = \min\{p_e : e \in E,\ p_e \ne0\}.

Notice that in the deterministic case, the latter algorithm is a 2T2T-approximation, which comes close to the lower bound in Theorem 2. We remark that none of the algorithms above actually requires GG to be transitive.

For the special case of total order, that is, if GG forms a (acyclic) tournament (for every u,v∈Vu,v \in V either (u,v)∈E(u,v) \in E or (v,u)∈E(v,u) \in E), or equivalently, if R(E)\mathcal{R}(E) is a path on VV, in the deterministic setting, the optimal policy is computable in FPT time.

Theorem 5. If GG is a (acyclic) tournament, assuming pe=1p_e=1 and τe>0\tau_e>0 for every e∈Ee \in E, the probing set with maximum weight can be computed in time 2O(Tlog⁡T)⋅nO(1)2^{O(T\log T)} \cdot n^{O(1)}.

Related work

In the Pandora’s Box problem (PBP), as in DVP, each item has an associated probing cost and a random reward. However, the objective is to maximize the expected maximum sampled reward minus the total probing cost. An optimal policy can be found in polynomial time for tree-like precedences [BFLL20, Wei79], however, it is NP-hard to approximate PBP above a factor 0.9997 for general precedences or matroid constraints.

PBP belongs to the family utility/disutility-optimization problems, for which there are generic greedy constant-factor approximation algorithms [20]. Similarly, if the objective function of a stochastic problem is adaptive submodular (the probabilistic equivalent of submodular functions), which is unfortunately not the case for DVP, there are simple greedy policies that are constant-factor approximations [9].

Another problem similar to DVP is the Stochastic Probing problem [11]. Here, as in DVP, every element to be probed has a weight and a success probability, and the goal is to maximize the expected total weight of the successively probed elements. The rule is that during the entire probing process, the set of probed and successfully probed elements, respectively, must satisfy packing constraints like Knapsack or matroid constraints, and the approximation ratio of the policy in [11] depends on the complexity of the constraints. For example, if the sets have to belong to the intersection of kk matroids, the approximation ratio is Ω(1/k)\Omega(1/k).

The ss-tt-unreliability problem asks for the probability that a pair of vertices uu and vv become disconnected when each edge ee of a graph GG is independently removed with probability pep_e. By Proposition 10, it is the same as to ask, assuming T=∞T=\infty, whether the edge (u,v)(u,v) can successively be probed or not, so the problem can be helpful to provide success bounds for DVP algorithms. Unfortunately, the problem is #BIS-hard [FGV24], meaning that there is most likely no (randomized) PTAS for the problem [5].

Hardness results

We construct a parametrized and approximation-preserving reduction from kk-Clique and DkS, respectively. Both problems are strongly NP-hard and W[1]-hard [CFK^{+}15, GJ79, LMFB24].

We recall that in DkS, the goal is, given an undirected graph H=(U,F)H=(U,F), to find the induced subgraph of HH with kk vertices and with a maximum number of edges, that is, to find arg⁡max⁡S⊆U,∣S∣=kDen⁡(S)\arg\max_{S\subseteq U,|S|=k}\operatorname{Den}(S), where Den⁡(S):=∣F[S]∣/(k2)\operatorname{Den}(S):=|F[S]|/\binom{k}{2} is the density of SS (F[S]F[S] is the edge set of the subgraph induced by SS). The kk-Clique problem is to check whether the optimal solution to DkS is a clique. For a positive integer mm, we denote [m]:={1,2,…,m}[m]:=\{1,2,\ldots,m\}. For a set XX, ∣X∣|X| denotes its cardinality.

Let k∈Nk\in\mathbb{N} and consider an undirected graph H=(U,F)H=(U,F). Let D∈ND\in\mathbb{N} to be fixed later. We consider the DVP instance GH=(VH,EH)G_H=(V_H,E_H) with vertex and edge sets

VH={se}e∈F∪{tui}u∈Ui∈[D]∪{z}andEH={pe,ui}e∈F,e∼ui∈[D]∪{qui}u∈Ui∈[D]∪{re}e∈F,V_H=\{s_e\}_{e\in F}\cup\{t_u^i\}_{u\in U}^{i\in[D]}\cup\{z\}\quad\text{and}\quad E_H=\{p_{e,u}^i\}_{e\in F,e\sim u}^{i\in[D]}\cup\{q_u^i\}_{u\in U}^{i\in[D]}\cup\{r_e\}_{e\in F},
{#eq:??}
Example of a reduction from $k$-Clique to DVP for $k=3$

Figure 1. Example of a reduction from kk-Clique to DVP for k=3k=3. The green and red edges represent the optimal probes.

where edges are defined as pe,ui=(se,tui)p^{i}_{e,u}=(s_e,t^{i}_u) (where uu is incident to ee), qui=(tui,z)q^{i}_u=(t^{i}_u,z) and re=(se,z)r_e=(s_e,z). All edges in EHE_H have success probability and probing cost 1, the edges rer_e have weight 1, other edges in EHE_H have weight 0. Notice that only the edges rer_e can yield profit. To probe rer_e, where e={u,v}∈Fe=\{u,v\}\in F, it is necessary and sufficient to probe qwiq^{i}_w or pe,wip^{i}_{e,w} for every i∈[D]i\in[D] and every w∈{u,v}w\in\{u,v\}. Clearly, GHG_H is a transitive DAG.

Proof of Theorem 1. Set D=1D=1 and T=k+(k2)T=k+\binom{k}{2}. We show that the construction above is a parametrized reduction (see [4] for the definition) from kk-Clique to DVP. More precisely, we show that the graph HH has a kk-clique if and only if w(OPT)=(k2)w(\mathrm{OPT})=\binom{k}{2}, where OPT is the optimal solution (the edges in EHE_H removed by an optimal policy) of the DVP instance GHG_H. Let S:={u∈U:pe,ui∈OPTS:=\{u\in U:p^{i}_{e,u}\in\mathrm{OPT} for some e∈F}e\in F\}. Clearly, OPT′:=(OPT∖{pe,ui}u∈S,e∋u)∪{qui}u∈S\mathrm{OPT}' := (\mathrm{OPT}\setminus\{p^{i}_{e,u}\}_{u\in S,e\ni u})\cup\{q^{i}_u\}_{u\in S} is feasible and also optimal since w(OPT′)=w(OPT)=∣OPT∩{re}e∈F∣w(\mathrm{OPT}')=w(\mathrm{OPT})=|\mathrm{OPT}\cap\{r_e\}_{e\in F}| and ∣OPT′∣≤∣OPT∣|\mathrm{OPT}'|\leq|\mathrm{OPT}|.

Assume w(OPT′)≥(k2)w(\mathrm{OPT}')\geq\binom{k}{2}, and so ℓ:=∣OPT′∩{qu1}u∈U∣≤T−(k2)=k\ell:=|\mathrm{OPT}'\cap\{q^{1}_u\}_{u\in U}|\leq T-\binom{k}{2}=k. For each u∈Uu\in U, let Nu:={re∈OPT:u∈e}N_u:=\{r_e\in\mathrm{OPT}:u\in e\}. We have

k(k−1)≤2w(OPT′)=∑u∈U∣Nu∣≤ℓ(ℓ−1)≤k(k−1).k(k-1)\leq2w(\mathrm{OPT}')=\sum_{u\in U}|N_u|\leq\ell(\ell-1)\leq k(k-1).

The second inequality holds because there are at most ℓ\ell many vertices uu with Nu≠∅N_u\ne\varnothing and ∣Nu∩Nv∣≤1|N_u\cap N_v|\leq1 for every pair u,v∈Uu,v\in U. All inequalities are tight, so w(OPT′)=(k2)w(\mathrm{OPT}')=\binom{k}{2}, and we have exactly kk many vertices u∈Uu\in U with Nu≠∅N_u\ne\varnothing and ∣Nu∣=k−1|N_u|=k-1. Therefore, those vertices form a kk-clique in HH.

Conversely, if HH has a kk-clique S⊆FS\subseteq F, then probing the edges {se}e∈F[S]∪{qu1}u∈U\{s_e\}_{e\in F[S]}\cup\{q^{1}_u\}_{u\in U} needs exactly TT probes and yields a profit (∣S∣2=(k2))|S| \choose2=\binom{k}{2}, thus w(OPT′)≥(k2)w(\mathrm{OPT}')\geq\binom{k}{2}, and therefore w(OPT′)=(k2)w(\mathrm{OPT}')=\binom{k}{2} as shown above.

To derive the approximation hardness of DVP, we state the currently sharpest known (parametrized) inapproximability results known for DkS.

Proposition 6. We have the following hardness results for DkS:

  1. [13 Theorem 1]: Assuming the Almost-ETH, for any ε∈(0,1)\varepsilon\in(0,1) there is no polynomial-time algorithm such that, given an integer kk and any graph H=(U,F)H=(U,F) on nn vertices that contains at least one kk-clique, always output S⊆US\subseteq U with ∣S∣=k|S|=k such that Den⁡(S)>2−(log⁡n)1−ε\operatorname{Den}(S)>2^{-(\log n)^{1-\varepsilon}}

ii) [14 Theorem 2]: Assuming the SPCH, for every function f(k)=o(k)f(k)=o(k) and every function gg, there is no g(k)⋅nO(1)g(k)\cdot n^{O(1)}-time algorithm such that, given an integer kk and any graph H=(U,F)H=(U,F) on nn vertices that contains at least one kk-clique, always outputs S⊆US\subseteq U with ∣S∣=k|S|=k such that Den⁡(S)≥1f(k)\operatorname{Den}(S)\ge\frac{1}{f(k)}.

Proof of Theorem 2. Let S∗⊆US^*\subseteq U be an optimal solution of the DkS instance H=(U,F)H=(U,F). First, we guess the optimal number of edges m∗:=∣F[S∗]∣m^*:=|F[S^*]|2 and set D=⌈m∗/k⌉D=\lceil m^*/k\rceil and T=kD+m∗T=kD+m^*.

Let now OPT⊆EH\mathrm{OPT}\subseteq E_H be the optimal solution of the DVP instance GH=(VH,EH)G_H=(V_H,E_H). Probing all the edges in the set {se}e∈F[S∗]∪{qui}i∈[D],u∈S∗\{s_e\}_{e\in F[S^*]}\cup\{q_u^i\}_{i\in[D],u\in S^*} needs exactly TT probes and yields a profit m∗m^*, so w(OPT)≥m∗w(\mathrm{OPT})\ge m^*.

The reduction. Assume now that there is an α\alpha-approximation algorithm for DVP that probes E′⊆EHE'\subseteq E_H with w(E′)≥w(OPT)/α≥m∗/αw(E')\ge w(\mathrm{OPT})/\alpha\ge m^*/\alpha. For every edge pe,ui∈E′p_{e,u}^i\in E', we remove pe,uip_{e,u}^i from E′E' and add quiq_u^i to E′E' (unless it is already in E′E') at no additional probing cost. The resulting set E′′E'' is feasible since ∣E′′∣≤∣E′∣|E''|\le|E'| and we have w(E′′)=w(E′)w(E'')=w(E'). Let S={u∈U:qui∈E′′ ∀i∈[D]}S=\{u\in U:q_u^i\in E''\ \forall i\in[D]\}. We have ∣S∣≤T/D=k+m∗/D≤2k|S|\le T/D=k+m^*/D\le2k. Notice that s{u,v}∈E′′s_{\{u,v\}}\in E'' implies u,v∈Su,v\in S and therefore {u,v}∈F[S]\{u,v\}\in F[S], so ∣F[S]∣≥w(E′′)≥m∗/α|F[S]|\ge w(E'')\ge m^*/\alpha. Now take a subset S′⊆SS'\subseteq S of size kk uniformly at random. For every e∈F[S]e\in F[S], we have Pr⁡(e∈F[S′])≥k−12(2k−1)=14−O(1k)\Pr(e\in F[S'])\ge\frac{k-1}{2(2k-1)}=\frac14-O\left(\frac1k\right), so E[∣F[S′]∣]≥k−12(2k−1)⋅m∗α\mathbb{E}[|F[S']|]\ge\frac{k-1}{2(2k-1)}\cdot\frac{m^*}{\alpha} and therefore (4+O(1/k))⋅α⋅Den⁡(S′)≥Den⁡(S∗)(4+O(1/k))\cdot\alpha\cdot\operatorname{Den}(S')\ge\operatorname{Den}(S^*) in expectation. The computation of S′⊆SS'\subseteq S with maximum density can be derandomized in time O(k2nO(1))O(k^2n^{O(1)}) via the method of conditional expectations, see [16].

Proof of (1). Let δ∈(0,1)\delta\in(0,1) and assume that there is a polynomial-time algorithm that outputs, for any DVP instance G=(V,E)G=(V,E) (without loss of generality with we∈{0,1}w_e\in\{0,1\}, pe=τe=1p_e=\tau_e=1 for every e∈Ee\in E), a feasible solution E′⊆EE'\subseteq E with w(E′)≥w(OPT)⋅2−(log⁡n)1−δw(E')\ge w(\mathrm{OPT})\cdot2^{-(\log n)^{1-\delta}}, where OPT⊆E\mathrm{OPT}\subseteq E is an optimal solution of the instance.

Consider any DkS instance H=(U,F)H=(U,F) with ℓ=∣U∣>max⁡{22/δ+1,22/(1−δ)}\ell=|U|>\max\{2^{2/\delta+1},2^{2/(1-\delta)}\} which contains a kk-clique S∗S^*, i.e., Den⁡(S∗)=1\operatorname{Den}(S^*)=1, taking kk large enough such that k−12(2k−1)≥15\frac{k-1}{2(2k-1)}\ge\frac15. We have n=∣F∣+Dℓ+1≤(ℓ2)+⌈ℓ−12⌉ℓ+1≤ℓ2n=|F|+D\ell+1\le{\ell\choose2}+\lceil\frac{\ell-1}{2}\rceil\ell+1\le\ell^2. Applying the assumed algorithm on the reduction GHG_H, and using the bounds above, for ℓ\ell large enough, we get a set S′⊆US'\subseteq U with

Den⁡(S′)≥2−(log⁡n)1−δ⋅15Den⁡(S∗)≥15⋅2−(log⁡n)1−δ≥15⋅2−(log⁡ℓ2)1−δ>2−(log⁡ℓ)1−δ/2,\operatorname{Den}(S')\ge2^{-(\log n)^{1-\delta}}\cdot\frac15\operatorname{Den}(S^*)\ge\frac15\cdot2^{-(\log n)^{1-\delta}}\ge\frac15\cdot2^{-(\log\ell^2)^{1-\delta}}>2^{-(\log\ell)^{1-\delta/2}},

which is a contradiction to i) in Proposition 6. The last inequality follows from

2(log⁡ℓ)1−δ/25⋅2(log⁡ℓ2)1−δ=15⋅2(log⁡ℓ)1−δ/2−(2log⁡ℓ)1−δ=15⋅2(log⁡ℓ)1−δ((log⁡ℓ)δ/2−21−δ)≥15⋅22⋅(4−21−δ)>1.\frac{2^{(\log\ell)^{1-\delta/2}}}{5\cdot2^{(\log\ell^2)^{1-\delta}}}=\frac15\cdot2^{(\log\ell)^{1-\delta/2}-(2\log\ell)^{1-\delta}}=\frac15\cdot2^{(\log\ell)^{1-\delta}((\log\ell)^{\delta/2}-2^{1-\delta})}\ge\frac15\cdot2^{2\cdot(4-2^{1-\delta})}>1.

Proof of (2). Consider any functions f(n)=o(n)f(n)=o(\sqrt n) and gg, assume without loss of generality that ff is monotonic increasing. Assume there is an algorithm with running time g(T)⋅nO(1)g(T)\cdot n^{O(1)}, that outputs, for any DVP instance G=(V,E)G=(V,E) (without loss of generality with we∈{0,1}w_e\in\{0,1\}, τe=pe=1\tau_e=p_e=1 for every e∈Ee\in E) a feasible solution E′⊆EE'\subseteq E with w(E′)≥w(OPT)/f(T)w(E')\ge w(\mathrm{OPT})/f(T), where OPT\mathrm{OPT} is the optimal solution of the instance GG.

Consider any DkS instance H=(U,F)H=(U,F) which contains a kk-clique S∗S^*, i.e., Den⁡(S∗)=1\operatorname{Den}(S^*)=1, taking kk large enough to have k−12(2k−1)≥15\frac{k-1}{2(2k-1)}\ge\frac15. Applying the assumed algorithm on the reduction GHG_H, we get a set S′⊆US'\subseteq U with

Den⁡(S′)≥15f(T)⋅Den⁡(S∗)>15f(k2)\operatorname{Den}(S')\ge\frac{1}{5f(T)}\cdot\operatorname{Den}(S^*)>\frac{1}{5f(k^2)}

using the monotonicity of ff and the bound T<k2T < k^2. We have lim⁡n→∞5f(n2)n=lim⁡q→∞5f(q)q=0\lim_{n\to\infty}\frac{5f(n^2)}{n}=\lim_{q\to\infty}\frac{5f(q)}{\sqrt{q}}=0, so assuming the SPCH, we contradict ii) in Proposition 6.

The approximation algorithm

As assumed in Section 1, the only condition for a probing policy to be valid is that at any time an edge is probed, it must lie in the transitive reduction of the remaining graph and be unprobed. We give stronger static criteria to assess whether a subset or a specific edge e∈Ee \in E can be extracted by a valid policy or not.

Claim 7. For any acyclic edge set EE and any edge e∈Ee \in E, we have R(E)∖{e}⊆R(E∖{e})\mathcal{R}(E) \setminus\{e\} \subseteq\mathcal{R}(E \setminus\{e\}).

Proof. Let e∈Ee \in E and e′=(u,v)∈R(E)∖{e}e'=(u,v) \in\mathcal{R}(E) \setminus\{e\}. Since there is no uu-vv-path except (u,v)(u,v) in EE, there is also no uu-vv-path except (u,v)(u,v) in E∖{e}E \setminus\{e\}, so e′∈R(E∖{e})e' \in\mathcal{R}(E \setminus\{e\}).

We call a set R={e1,…,ek}⊆ER=\{e_1,\ldots,e_k\}\subseteq E obtainable if the elements of RR can be ordered in a way that e1∈R(E)e_1\in\mathcal{R}(E) and et∈R(E∖{e1,…,et−1})e_t\in\mathcal{R}(E\setminus\{e_1,\ldots,e_{t-1}\}) for every t∈{2,…,k}t\in\{2,\ldots,k\}. By the following lemma, obtainability is the essential static criterion for a set to be probable.

Lemma 8. For any valid probing policy, the set of successfully probed edges is always obtainable. Conversely, for any obtainable set R⊆ER\subseteq E, assuming τ(R)≤T\tau(R)\leq T and pe>0p_e>0 for every e∈Re\in R, there is a valid probing policy that successfully probes every edge in RR with non-zero probability.

Proof. The first part is clear from Claim 7 since any failed probed edge is never removed from EE. Consider now an obtainable set R={e1,…,ek}⊆ER=\{e_1,\ldots,e_k\}\subseteq E with pe>0p_e>0 for every e∈Re\in R sorted appropriately. Consider the policy π\pi that probes the elements of RR in the given order and halts as soon as the next candidate is not in the transitive reduction of the remaining graph or once all elements of RR have been probed. Since π\pi only probes edges in RR and τ(R)≤T\tau(R)\leq T by assumption, the budget never runs out before probing all edges in RR. In the event A=⋂i=1k{Ωei=1}A=\bigcap_{i=1}^{k}\{\Omega_{e_i}=1\}, π\pi probes every element of RR successfully. Since the random variables {Ωei}i∈[k]\{\Omega_{e_i}\}_{i\in[k]} are independent, we have P(A)=∏i=1kpei>0\mathbb{P}(A)=\prod_{i=1}^{k}p_{e_i}>0 and the claim follows.

Lemma 9. For any acyclic edge set EE and any set R⊆ER\subseteq E, RR is obtainable if and only if there is no uu-vv-path in E∖RE\setminus R for every edge (u,v)∈R(u,v)\in R.

Proof. We argue by induction in ∣R∣|R|. The case ∣R∣=1|R|=1 is precisely the definition of R(E)\mathcal{R}(E). Assume now ∣R∣>1|R|>1. If RR is obtainable and e=(u,v)e=(u,v) is the last element that was added to RR, R′=R∖{e}R'=R\setminus\{e\} is obtainable by assumption and there is no u′u'-v′v'-path in E∖RE\setminus R for any (u′,v′)∈R′(u',v')\in R' by induction. Since e∈R(E∖R′)e\in\mathcal{R}(E\setminus R'), there is also no uu-vv-path in E∖RE\setminus R, so e∈R(E∖R′)e\in\mathcal{R}(E\setminus R').

Assume now that there is no uu-vv-path in E∖RE\setminus R for every e=(u,v)∈Re=(u,v)\in R. Let e′=(u′,v′)∈Re'=(u',v')\in R be the edge in RR such that the u′u'-v′v'-path in EE is the longest among all edges in RR. Let R′=R∖{e′}R'=R\setminus\{e'\}. For any (u,v)∈R′(u,v)\in R', e′e' cannot be in any uu-vv-path since we could construct a uu-vv-path longer than the u′u'-v′v'-path, so there is no uu-vv-path in E∖R′E\setminus R', meaning that R′R' is obtainable by induction. By the same argument, e′∈R(E∖R′)e'\in\mathcal{R}(E\setminus R'), so RR is obtainable.

With this criterion, we can draw a similarity between obtainability and the Min-Cut problem. We recall that for any directed graph G=(V,E)G=(V,E) with {u,v}⊆V\{u,v\}\subseteq V, an edge set C⊆EC\subseteq E is an uu-vv-cut if there is a vertex set {u}⊆U⊆V∖{v}\{u\}\subseteq U\subseteq V\setminus\{v\} such that C=δ+(U)C=\delta^+(U), where δ+(U)\delta^+(U) denotes the set of all edges from UU to V∖UV\setminus U.

Proposition 10. Let EE be an acyclic edge set and let e=(u,v)∈Ee=(u,v)\in E. Any obtainable set R⊆ER\subseteq E with e∈Re\in R contains a uu-vv-cut and any uu-vv-cut is obtainable.

Proof. Let R⊆ER\subseteq E with e∈Re\in R be obtainable. By Lemma 9, there are no uu-vv-paths in E∖RE\setminus R. Let U={w∈V:∃ uU=\{w\in V:\exists\ u-ww-path in E∖R}E\setminus R\}. Clearly, δ+(U)\delta^{+}(U) is a uu-vv-cut since u∈Uu\in U and v∉Uv\notin U and δ+(U)⊆R\delta^{+}(U)\subseteq R.

Let CC be an uu-vv-cut with {u}⊆U⊆V∖{v}\{u\}\subseteq U\subseteq V\setminus\{v\} such that C=δ+(U)C=\delta^{+}(U). Assume that CC is not obtainable, meaning by Lemma 9 there is an edge e′=(u′,v′)∈Ce'=(u',v')\in C and an u′u'-v′v'-path P⊆VP\subseteq V with no edge in CC. Since e′∈δ+(U)e'\in\delta^{+}(U), we have u′∈Uu'\in U but v′∉Uv'\notin U. Let w∈Pw\in P be the last vertex in PP such that the subpath of PP from u′u' to ww lies entirely in UU. The vertex ww exists since u′∈Uu'\in U and w≠v′w\ne v' since v′∉Uv'\notin U. Therefore the successor w′∈Pw'\in P of ww in PP exists and w′∉Uw'\notin U, in particular (w,w′)∈δ+(U)=C(w,w')\in\delta^{+}(U)=C, which is a contradiction. □\square

It follows immediately from Proposition 10 that an inclusion-minimal obtainable set containing e=(u,v)e=(u,v) is an inclusion-minimal uu-vv-cut and vice versa. In particular, computing an optimal minimum-cost obtainable set including ee is equivalent to computing a minimum uu-vv-cut on the same graph with capacities (τe)e∈E(\tau_e)_{e\in E}, which is achievable in time O(nm)O(nm), see [18].

For the analysis of a policy, we first need to assure that some probabilistic notions are well-defined, especially for an optimal policy. While we allow policies to sample other random variables than {Ωe}e∈E\{\Omega_e\}_{e\in E}, we ensure that this is not necessary for optimality. For any policy π\pi and any e∈Ee\in E, let Ae,πA_{e,\pi} refer to the event that π\pi probes ee and let Be:={Ωe=1}B_e:=\{\Omega_e=1\}.

Lemma 11. For every DVP instance G=(V,E)G=(V,E), there exists an optimal policy π∗\pi^* that only depends on the variables {Ωe}e∈E\{\Omega_e\}_{e\in E} and such that the events Ae,π∗A_{e,\pi^*} and BeB_e are independent for every e∈Ee\in E.

Proof. For a DVP instance G=(V,E)G=(V,E), let [H,F,T][H,F,T] denote a stage of a probing process where HH is the set of unprobed edges, FF of failed probed edges and TT the leftover budget. Let X(H,F,T):=R(H∪F)∩{e∈H:τe≤T}X(H,F,T):=R(H\cup F)\cap\{e\in H:\tau_e\le T\} be the set of probable edges and let W(H,F,T)W(H,F,T) be the optimal expected profit. As argued in [7], W(H,F,T)W(H,F,T) is computable with the Bellman recursion W(H,F,T)=0W(H,F,T)=0 if X(H,F,T)=∅X(H,F,T)=\varnothing and

W(H,F,T)=max⁡e∈X(H,F,T)(pe(we+W(H∖{e},F,T−τe))+(1−pe)W(H∖{e},F∪{e},T−τe))(1)W(H,F,T)=\max_{e\in X(H,F,T)}\left(p_e\left(w_e+W(H\setminus\{e\},F,T-\tau_e)\right)+(1-p_e)W(H\setminus\{e\},F\cup\{e\},T-\tau_e)\right) \tag*{(1)}

otherwise. Therefore, we can select π∗\pi^* to be a policy that, at every stage [H,F,T][H,F,T], picks an edge that maximizes (1), breaking ties deterministically, meaning that π∗\pi^* depends only on {Ωe}e∈E\{\Omega_e\}_{e\in E}.

For a stage S=[H,F,T]S=[H,F,T], let CSC_S be the event that the policy attains the stage SS. By induction in the number of probes, for every stage S=[H,F,T]S=[H,F,T], we have either CS=∅C_S=\varnothing or CS=⋂e∈E∖(H∪F)Be∩⋂e′∈FB‾e′C_S=\bigcap_{e\in E\setminus(H\cup F)}B_e\cap\bigcap_{e'\in F}\overline{B}_{e'}. In both cases, for every e∈He\in H, BeB_e and CSC_S are independent. If SS and S′S' are two stages where π∗\pi^* picks ee, we have CS∩CS′=∅C_S\cap C_{S'}=\varnothing since an edge is never picked twice. Since the event Ae,π∗A_{e,\pi^*} is the event that such a stage is attained, Ae,π∗A_{e,\pi^*} and BeB_e are independent. □\square

It follows that the expected profit of any policy π\pi can be formally reformulated as ∑e∈EweP(Ae,π∩Be)=∑e∈EweP(Ae,π)P(Be)\sum_{e\in E}w_e\mathbb{P}(A_{e,\pi}\cap B_e)=\sum_{e\in E}w_e\mathbb{P}(A_{e,\pi})\mathbb{P}(B_e).

An adaptive policy for uniform probabilities. If a DVP instance has exactly one edge ee with we>0w_e>0, an optimal policy for that instance is coincidentally a policy which has the highest chance of probing ee. By Lemma 11, we can assume that this policy only depends on {Ωe}e∈E\{\Omega_e\}_{e\in E}. For any policy π\pi, we write θ(e,π):=P(Ae,π)\theta(e,\pi):=\mathbb{P}(A_{e,\pi}) and call π\pi ee-optimal if π∈arg⁡max⁡π′θ(e,π′)\pi\in\arg\max_{\pi'}\theta(e,\pi'), i.e., if π\pi has the highest chance of probing ee among all feasible policies.

Intuitively, for any (globally) optimal policy π∗\pi^{*}, if we know the edge e∗e^{*} with highest expected profit among all edges in EE and we know an e∗e^{*}-optimal policy π\pi, π\pi will extract at least as much (expected) profit from e∗e^{*} as π∗\pi^{*} but potentially nothing from the other m−1m-1 edges; therefore, uniformly sampling a single edge e∈Ee \in E and running an ee-optimal policy is an mm-approximation (in expectation) of an optimal policy. We now derive a simple e′e'-optimal policy for any edge e′e' in a DVP instance G=(V,E)G=(V,E) in the case of uniform costs and probabilities.

Lemma 12. Let p∈(0,1]p \in(0,1] and let G=(V,E)G=(V,E) be a DVP instance with τe=1\tau_e=1 and pe=pp_e=p for every e∈Ee \in E. Consider an edge e=(s,t)∈Ee=(s,t) \in E. A policy which, at any step, probes an edge on a minimum ss-tt-cut (consisting of unprobed edges only), is ee-optimal, regardless of the choice of the cut and the edge.

Proof. Without loss of generality, we assume T<mT<m since otherwise, probing any edges (as long as any edge is probable) is trivially an optimal policy.

We again denote a stage of the probing process where HH is the set of unprobed edges, FF the set of failed probed edges and TT the leftover budget as [H,F,T][H,F,T], or [H,F][H,F] if we omit the budget. If we probe e∈He \in H at the stage [H,F,T][H,F,T], if the probe succeeds, we are at stage [H∖{e},F,T−1][H\setminus\{e\},F,T-1], and at [H∖{e},F∪{e},T−1][H\setminus\{e\},F\cup\{e\},T-1] otherwise. At stage [H,F][H,F], let σ(H,F)\sigma(H,F) be the size of a minimum admissible ss-tt-cut. We say that an ss-tt-cut is admissible if it which contains only edges in HH; We set σ(H,F)=+∞\sigma(H,F)=+\infty if no admissible ss-tt-cut exists, i.e., if FF contains an ss-tt-path.3

At any stage [H,F][H,F], let e∈He \in H be in a minimum admissible ss-tt-cut CC. C∖{e}C\setminus\{e\} is an admissible ss-tt-cut at [H∖{e},F][H\setminus\{e\},F], so σ(H∖{e},F)≤σ(H,F)−1\sigma(H\setminus\{e\},F)\leq\sigma(H,F)-1. However, if C′C' is an admissible ss-tt-cut at [H∖{e},F][H\setminus\{e\},F], C′∪{e}C'\cup\{e\} is a cut at [H,F][H,F], so σ(H∖{e},F)=σ(H,F)−1\sigma(H\setminus\{e\},F)=\sigma(H,F)-1. We have σ(H∖{e},F∪{e})≥σ(H,F)\sigma(H\setminus\{e\},F\cup\{e\})\geq\sigma(H,F) since any admissible ss-tt-cut at [H∖{e},F∪{e}][H\setminus\{e\},F\cup\{e\}] is an admissible ss-tt-cut at [H,F][H,F].

At [H,F][H,F], let e∈He \in H not lie on any admissible minimum ss-tt-cut. Any minimum admissible ss-tt-cut CC (without ee) at [H,F][H,F] is also a minimum admissible ss-tt-cut at [H∖{e},F∪{e}][H\setminus\{e\},F\cup\{e\}] and vice versa, so σ(H∖{e},F∪{e})=σ(H,F)\sigma(H\setminus\{e\},F\cup\{e\})=\sigma(H,F). Let C′C' be a minimum admissible ss-tt-cut at the stage [H∖{e},F][H\setminus\{e\},F]. Since C′C' disconnects ss and tt in (H∖{e})∪F(H\setminus\{e\})\cup F, C′∪{e}C'\cup\{e\} disconnects ss and tt in H∪FH\cup F as well. However, since ee lies on no minimum admissible ss-tt-cut at the stage [H,F][H,F], C′∪{e}C'\cup\{e\} has no minimum cardinality at stage [H,F][H,F], so we have σ(H∖{e},F)=∣C′∣>σ(H,F)−1\sigma(H\setminus\{e\},F)=|C'|>\sigma(H,F)-1. Since any admissible ss-tt-cut (without ee) at [H,F][H,F] is an admissible ss-tt-cut in [H∖{e},F][H\setminus\{e\},F], we have σ(H∖{e},F)≤σ(H,F)\sigma(H\setminus\{e\},F)\leq\sigma(H,F), so we get σ(H∖{e},F)=σ(H,F)\sigma(H\setminus\{e\},F)=\sigma(H,F).

Let P∗(H,F,T)P^{*}(H,F,T) be the success probability of an optimal policy at that stage. By Proposition 10, the algorithms succeed if we managed to disconnect ss and tt, so we have P∗(H,F,T)=1P^{*}(H,F,T)=1 if and only if σ(H,F)=0\sigma(H,F)=0. As shown above, σ(H,F)\sigma(H,F) can only decrease by 1 at each probe, we have P∗(H,F,T)=0P^{*}(H,F,T)=0 if T<σ(H,F)T<\sigma(H,F). For any e∈He\in H, let Pe(H,F,T)P_e(H,F,T) be the success probability of an optimal policy at the next stage, assuming ee is picked at the current stage. Therefore, Pe(H,F,T)=p⋅P∗(H∖{e},F,T−1)+(1−p)⋅P∗(H∖{e},F∪{e},T−1)P_e(H,F,T)=p\cdot P^{*}(H\setminus\{e\},F,T-1)+(1-p)\cdot P^{*}(H\setminus\{e\},F\cup\{e\},T-1). In particular, a policy is optimal if, at any stage (H,F,T)(H,F,T), it probes an arbitrary edge in arg⁡max⁡e∈HPe(H,F,T)\arg\max_{e\in H}P_e(H,F,T).

By induction in TT, we show that at any stage [H,F,T][H,F,T] with T≥σ(H,F)>0T\geq\sigma(H,F)>0, any edge on any minimum admissible ss-tt-cut is in arg⁡max⁡e∈HPe(H,F,T)\arg\max_{e\in H}P_e(H,F,T); the lemma follows immediately. If T=1T=1, we have σ(H,F)=1\sigma(H,F)=1, and the only way to reduce σ(H,F)\sigma(H,F) is to pick the edge on the (unique) admissible single-edge ss-tt-cut. Assume now T>1T>1.

At a stage [H,F,T][H,F,T], let f∈arg⁡max⁡e∈HPe(H,F,T)f\in\arg\max_{e\in H}P_e(H,F,T) be the edge chosen by an optimal policy. If ff belongs to a minimum admissible ss-tt-cut, the claim follows directly by induction; otherwise, let CC be any minimum admissible ss-tt-cut. Since CC is obtainable by Proposition 10, there exists some edge e′∈R(H∪F)∩Ce' \in\mathcal{R}(H \cup F) \cap C. As argued above, CC is a minimum admissible ss-tt-cut at the stages [H∖{f}),F][H \setminus\{f\}), F] and [H∖{f}),F∪{f}][H \setminus\{f\}), F \cup\{f\}], so e′∈arg⁡max⁡e∈HPe(H∖{f},F,T−1)e' \in\arg\max_{e \in H} P_e(H \setminus\{f\}, F, T - 1) and e′∈arg⁡max⁡e∈HPe(H∖{f},F∪{f},T−1)e' \in\arg\max_{e \in H} P_e(H \setminus\{f\}, F \cup\{f\}, T - 1) by induction. We get

P∗(H,F,T)=Pf(H,F,T)=p⋅P∗(H∖{f},F,T−1)+(1−p)⋅P∗(H∖{f},F∪{f},T−1)=p⋅Pe′(H∖{f},F,T−1)+(1−p)⋅Pe′(H∖{f},F∪{f},T−1)=p2⋅P∗(H∖{e′,f},F,T−2)+p(1−p)⋅(P∗(H∖{e′,f},F∪{f},T−2)+P∗(H∖{e′,f},F∪{e′},T−2))+(1−p)2⋅P∗(H∖{e′,f},F∪{e′,f},T−2)=p⋅Pf(H∖{e′},F,T−1)+(1−p)⋅Pf(H∖{e′},F∪{e′},T−1)≤p⋅P∗(H∖{e′},F,T−1)+(1−p)⋅P∗(H∖{e′},F∪{e′},T−1)=Pe′(H,F,T),\begin{aligned} P^*(H,F,T) &= P_f(H,F,T) \\ &= p \cdot P^*(H \setminus\{f\},F,T-1) + (1-p) \cdot P^*(H \setminus\{f\},F \cup\{f\},T-1) \\ &= p \cdot P_{e'}(H \setminus\{f\},F,T-1) + (1-p) \cdot P_{e'}(H \setminus\{f\},F \cup\{f\},T-1) \\ &= p^2 \cdot P^*(H \setminus\{e',f\},F,T-2) \\ &\quad+ p(1-p) \cdot\left(P^*(H \setminus\{e',f\},F \cup\{f\},T-2) + P^*(H \setminus\{e',f\},F \cup\{e'\},T-2)\right) \\ &\quad+ (1-p)^2 \cdot P^*(H \setminus\{e',f\},F \cup\{e',f\},T-2) \\ &= p \cdot P_f(H \setminus\{e'\},F,T-1) + (1-p) \cdot P_f(H \setminus\{e'\},F \cup\{e'\},T-1) \\ &\le p \cdot P^*(H \setminus\{e'\},F,T-1) + (1-p) \cdot P^*(H \setminus\{e'\},F \cup\{e'\},T-1) \\ &= P_{e'}(H,F,T), \end{aligned}

meaning e′∈arg⁡max⁡e∈HPe(H,F,T)e' \in\arg\max_{e \in H} P_e(H,F,T). Since the choice of CC and e′e' was arbitrary, the proof is complete.

Proof of Theorem 3. Let ZZ be a random variable which is uniformly distributed over EE and independent of {Ωe}e∈E\{\Omega_e\}_{e \in E}. We consider the policy π~\tilde{\pi} which first samples an edge e~\tilde{e} from ZZ, then runs the e~\tilde{e}-optimal policy πe~\pi_{\tilde{e}} of Lemma 12. Since Ae,π~⊇{Z=e}∩Ae,πeA_{e,\tilde{\pi}} \supseteq\{Z=e\} \cap A_{e,\pi_e}, and the events {Z=e}\{Z=e\}, Ae,πeA_{e,\pi_e} and BeB_e are independent for every e∈Ee \in E, we get expected profit

W(π~)=∑e∈EweP(Be∩Ae,π~)≥∑e∈EweP(Z=e)P(Be)P(Ae,πe)=∑e∈Epwemθ(e,πe)≥1m∑e∈Epweθ(e,π∗)=opt⁡m.\begin{aligned} W(\tilde{\pi}) = \sum_{e \in E} w_e \mathbb{P}(B_e \cap A_{e,\tilde{\pi}}) \\ &\ge\sum_{e \in E} w_e \mathbb{P}(Z=e)\mathbb{P}(B_e)\mathbb{P}(A_{e,\pi_e}) = \sum_{e \in E} \frac{p w_e}{m}\theta(e,\pi_e) \ge\frac{1}{m}\sum_{e \in E} p w_e \theta(e,\pi^*) = \frac{\operatorname{opt}}{m}. \end{aligned}

Any sampled ee-optimal policy makes up to TT probes (since we assumed T<mT < m) and updates the transitive reduction and the minimum cut at each iteration in time O(m+n1.528)O(m+n^{1.528}) and O(mn)O(mn) respectively, yielding a total time of at most O(Tmn)O(Tmn).

A policy for general instances. The first step of the algorithm is, for every e∈Ee \in E, to compute a minimum-cost obtainable set Se⊆ES_e \subseteq E with e∈See \in S_e. Recall that we also assume pe>0p_e > 0 for every e∈Ee \in E since we can assign cost τe=T+1\tau_e = T+1 to any edge with pe=0p_e=0 since an optimal policy would never probe an edge with success probability 0.

Every edge e∈Ee \in E is treated as an object with size τ~e:=τ(Se)\tilde{\tau}_e := \tau(S_e) and profit w~e:=we∏f∈Sepf\tilde{w}_e := w_e \prod_{f \in S_e} p_f, and the goal is to pick objects with maximum profit but bounded cumulative size, like a Knapsack instance. We assign to every e∈Ee \in E a cost efficiency ratio re:=w~eτ~er_e := \frac{\tilde{w}_e}{\tilde{\tau}_e}.

We order the edges in EE in decreasing cost efficiency ratio but exclude the edges with τ~e>T\tilde{\tau}_e > T, thus having E={e1,e2,…,em}E = \{e_1,e_2,\ldots,e_m\} with rek≥rek+1r_{e_k} \ge r_{e_{k+1}} for every k∈[m−1]k \in[m-1]. Let κ=m\kappa= m if ∑i=1mτ~ei≤T\sum_{i=1}^{m}\tilde{\tau}_{e_i} \le T and otherwise be the integer with ∑i=1κτ~ei≤T<∑i=1κ+1τ~ei\sum_{i=1}^{\kappa}\tilde{\tau}_{e_i} \le T < \sum_{i=1}^{\kappa+1}\tilde{\tau}_{e_i}. Let also eˉ\bar{e} be the edge with maximum profit, i.e., eˉ∈arg⁡max⁡e∈Ew~e\bar{e} \in\arg\max_{e \in E} \tilde{w}_e.

From this point on, the algorithm is greedy. We set E′:=⋃i=1κSeiE' := \bigcup_{i=1}^{\kappa} S_{e_i} if ∑i=1κτ~ei≥τ~eˉ\sum_{i=1}^{\kappa}\tilde{\tau}_{e_i} \ge\tilde{\tau}_{\bar{e}} and E′:=SeˉE' := S_{\bar{e}} otherwise. Then, we probe any probeable edge in E′E' in arbitrary order until no edge in E′E' can be probed, i.e., all unprobed edges in E′E' are not in the transitive reduction of the resulting graph. Proof of Theorem 4. Let π\pi denote the policy described above. In the case ∑i=1mτ~ei≥τ~eˉ\sum_{i=1}^{m} \widetilde{\tau}_{e_i} \ge\widetilde{\tau}_{\bar{e}}, notice that for any i∈[κ]i \in[\kappa], in the event ⋂f∈Sei∖{e}Bf\bigcap_{f \in S_{e_i}\setminus\{e\}} B_f, eie_i is successfully probed; in particular, we have θ(ei,π)≥P(⋂f∈Sei∖{ei}Bf)=1pei∏f∈Seipf\theta(e_i,\pi) \ge\mathbb{P}\left(\bigcap_{f \in S_{e_i}\setminus\{e_i\}} B_f\right) = \frac{1}{p_{e_i}}\prod_{f \in S_{e_i}} p_f. By the same argument, we have θ(eˉ,π)≥1peˉ∏f∈Seˉpf\theta(\bar{e},\pi) \ge\frac{1}{p_{\bar{e}}}\prod_{f \in S_{\bar{e}}}p_f when ∑i=1mτ~ei<τ~eˉ\sum_{i=1}^{m}\widetilde{\tau}_{e_i} < \widetilde{\tau}_{\bar{e}}.

Let π∗\pi^* be an optimal (adaptive) probing policy as in Lemma 11 and let x∗=θ(e,π∗)x^* = \theta(e,\pi^*) for every e∈Ee \in E. We have W(π∗)=∑e∈Epewexe∗W(\pi^*) = \sum_{e \in E}p_e w_e x_e^*. Since π∗\pi^* is feasible, the cumulative cost of the edges probed by π∗\pi^* is never above TT, i.e., ∑e∈Eτe1Ae≤T\sum_{e \in E}\tau_e\mathbf{1}_{A_e} \le T. This must thus hold in expectation as well, so T≥E[∑e∈Eτe1Ae]=∑e∈Eτexe∗T \ge\mathbb{E}\left[\sum_{e \in E}\tau_e\mathbf{1}_{A_e}\right] = \sum_{e \in E}\tau_e x_e^*. Consider the linear program

L:=max⁡{∑e∈Ew~eye:0≤y≤1, ∑e∈Eτ~eye≤T}(2)L := \max\left\{\sum_{e \in E}\widetilde{w}_e y_e : 0 \le y \le1,\ \sum_{e \in E}\widetilde{\tau}_e y_e \le T\right\} \tag*{(2)}

For every e∈Ee \in E, notice that (xe∗/T)e∈E(x_e^*/T)_{e \in E} is a feasible fractional solution with respect to the LP (2) since ∑e∈Eτ(Se)(xe∗/T)≤∑e∈Eτexe∗≤T\sum_{e \in E}\tau(S_e)(x_e^*/T) \le\sum_{e \in E}\tau_e x_e^* \le T. Also, ∣Se∖{e}∣≤τ(Se)≤T|S_e \setminus\{e\}| \le\tau(S_e) \le T, so ∏f∈Se∖{e}pf≥pmin⁡∣Se∣−1≥pmin⁡T−1\prod_{f \in S_e\setminus\{e\}}p_f \ge p_{\min}^{|S_e|-1} \ge p_{\min}^{T-1} and w~e≥pmin⁡Twe\widetilde{w}_e \ge p_{\min}^{T}w_e. Together, we get L≥pmin⁡TTW(π∗)L \ge\frac{p_{\min}^{T}}{T}W(\pi^*).

One fractional optimum y∗y^* of (2) is yei∗=1y^*_{e_i}=1 for i≤κi \le\kappa, yeκ+1∗=1−∑i=1κyei∗y^*_{e_{\kappa+1}}=1-\sum_{i=1}^{\kappa}y^*_{e_i} and yei∗=0y^*_{e_i}=0 for i>κ+1i>\kappa+1, with EE sorted as above since (2) has the form of the canonical LP relaxation of the 0-1 Knapsack problem [15]. In particular, we have ∑i=1κw~ei+w~eˉ≥∑i=1κ+1w~ei≥L\sum_{i=1}^{\kappa}\widetilde{w}_{e_i}+\widetilde{w}_{\bar{e}}\ge\sum_{i=1}^{\kappa+1}\widetilde{w}_{e_i}\ge L.

Assume now that ∑i=1κw~ei≥w~eˉ\sum_{i=1}^{\kappa}\widetilde{w}_{e_i}\ge\widetilde{w}_{\bar{e}}, the other case is symmetric. By construction, for any i∈[κ]i\in[\kappa], eie_i is probed if ∏f∈SeiΩf=1\prod_{f\in S_{e_i}}\Omega_f=1, so eie_i is probed and succeeds with probability at most pei∏f∈Seipfp_{e_i}\prod_{f\in S_{e_i}}p_f. By the linearity of expectation, the total expected profit is

W(π)=∑i=1κweipeiθ(ei,π)=∑i=1κw~ei≥12(∑i=1κw~ei+w~eˉ)≥L2≥pmin⁡T2TW(π∗).W(\pi)=\sum_{i=1}^{\kappa}w_{e_i}p_{e_i}\theta(e_i,\pi)=\sum_{i=1}^{\kappa}\widetilde{w}_{e_i}\ge\frac{1}{2}\left(\sum_{i=1}^{\kappa}\widetilde{w}_{e_i}+\widetilde{w}_{\bar{e}}\right)\ge\frac{L}{2}\ge\frac{p_{\min}^{T}}{2T}W(\pi^*).

Computing SeS_e for every e∈Ee\in E can be achieved in time O(m2n)O(m^2n) since it consists of computing a Min-Cut instance for every edge. Then, during the probing process, R(E)\mathcal{R}(E) can be updated in time O(m+n1.528)O(m+n^{1.528}) at each probe, and the choice of the probe in E′E' is arbitrary, the total running time is bounded by O(m2n)O(m^2n).

The algorithm for total orders

We give an FPT algorithm parameterized in the budget TT for instances G=(V,E)G=(V,E) that form a tournament, as defined in § 1. For simplicity, we order V={v1,…,vn}V=\{v_1,\ldots,v_n\} such that for any i,j∈[m]i,j\in[m], we have (vi,vj)∈E(v_i,v_j)\in E if and only if i<ji<j. In this setting, the following lemma follows directly from Lemma 9.

Lemma 13. Let R⊆ER\subseteq E be obtainable. For every e=(vi,vj)∈Re=(v_i,v_j)\in R, we have j−i≤∣R∣j-i\le|R|.

Proof. By Lemma 9, for (vi,vj)∈R(v_i,v_j)\in R, for any i<k<ji<k<j, the viv_i-vjv_j-path (vi,vk,vj)(v_i,v_k,v_j) cannot be in E∖RE\setminus R, so (vi,vk)∈R(v_i,v_k)\in R or (vk,vj)∈R(v_k,v_j)\in R. In particular, ∣R∖{e}∣=j−i−1|R\setminus\{e\}|=j-i-1, and the claim follows.

The main observation is that for any obtainable set R⊆ER\subseteq E with τ(R)≤T\tau(R)\le T, we can divide GG into up to TT disjoint blocks of T2+1T^2+1 consecutive vertices such that every edge in RR lies in exactly one of those blocks. We define the (s,t)(s,t)-block Bs,tB_{s,t} to be the edge set of the induced subgraph of GG on the vertex set {vs,…,vt}\{v_s,\ldots,v_t\}.

Lemma 14. Let R∈ER \in E be obtainable with τ(R)≤T\tau(R) \le T. There is a family B\mathcal{B} of up to TT disjoint blocks such that t−s≤T2t-s \le T^2 for each block Bs,t∈BB_{s,t} \in\mathcal{B} and R⊆⋃B∈BBR \subseteq\bigcup_{B \in\mathcal{B}} B. Furthermore, for every block B∈BB \in\mathcal{B}, R∩BR \cap B is obtainable.

Proof. Consider the graph H=(R,Z)H=(R,Z) with ZZ defined as follows: For every e=(vi,vj),f=(vk,vℓ)∈Re=(v_i,v_j), f=(v_k,v_\ell) \in R, we have {e,f}∈Z\{e,f\} \in Z whenever j≥kj \ge k and ℓ≥i\ell\ge i.

Let X={(vi1,vj1),…,(vir,vjr)}⊆RX=\{(v_{i_1},v_{j_1}),\ldots,(v_{i_r},v_{j_r})\}\subseteq R be a connected component of HH of size rr, and let s(X):=min⁡t∈[r]its(X):=\min_{t\in[r]}i_t and t(X):=max⁡t∈[r]jtt(X):=\max_{t\in[r]}j_t. By Lemma 13, we have jt−it≤∣R∣≤Tj_t-i_t\le|R|\le T for every t∈[r]t\in[r], so t(X)−s(X)≤Tr≤T2t(X)-s(X)\le Tr\le T^2 by induction. For (vk,vℓ)∈R∖X(v_k,v_\ell)\in R\setminus X, we have either k>t(X)k>t(X) or ℓ<s(X)\ell<s(X). In particular, if YY is another connected component of HH, we have s(Y)>t(X)s(Y)>t(X) or t(Y)<s(X)t(Y)<s(X), so the blocks Bs(X),t(X)B_{s(X),t(X)} and Bs(Y),t(Y)B_{s(Y),t(Y)} are disjoint. For any (vi,vj)∈R(v_i,v_j)\in R in the connected component XX of HH, any ii-jj-path on EE lies in Bs(X),t(X)B_{s(X),t(X)} meaning that E∖RE\setminus R contains an ii-jj-path if and only if Bs(X),t(X)∖RB_{s(X),t(X)}\setminus R contains an ii-jj-path. By Lemma 9, this means that every connected component of HH is obtainable. Trivially HH has up to ∣R∣≤T|R|\le T connected components.

Therefore, if A\mathcal{A} is the set of connected components of HH, we can choose B={Bs(X),t(X)}X∈A\mathcal{B}=\{B_{s(X),t(X)}\}_{X\in\mathcal{A}} as the family of blocks which satisfies the properties of the claim.

We now describe the algorithm of Theorem 5.

Proof of Theorem 5. Let OPTs,t,T′∈arg⁡max⁡{R⊆Bs,t; R is obtainable and τ(R)≤T′}\mathrm{OPT}_{s,t,T'}\in\arg\max\{R\subseteq B_{s,t};\ R\text{ is obtainable and }\tau(R)\le T'\} refer to an optimal solution of the DVP instance restricted on the block Bs,tB_{s,t} and budget T′T'. Clearly, OPT1,n,T\mathrm{OPT}_{1,n,T} is an optimal solution for the entire instance. If t−s≤T2t-s\le T^2, there are at most 2O(T′log⁡T)2^{O(T'\log T)} many candidates for OPTs,t,T′\mathrm{OPT}_{s,t,T'} since Bs,tB_{s,t} has ℓ=(t−s+12)≤(T2+12)≤T4\ell=\binom{t-s+1}{2}\le\binom{T^2+1}{2}\le T^4 edges and there are there are at most (ℓT′)≤ℓT′≤T4T′≤2O(T′log⁡T)\binom{\ell}{T'}\le\ell^{T'}\le T^{4T'}\le2^{O(T'\log T)} obtainable sets in Bs,tB_{s,t}.

We show now that for every k∈[n]k\in[n] and T′∈[T]T'\in[T], OPT1,k,T′\mathrm{OPT}_{1,k,T'} can be selected via the recursion

OPT1,k,T′∈arg⁡max⁡k−T2≤s≤k, T′′≤T′{w(OPT1,s−1,T′−T′′∪OPTs,k,T′′)}.(3)\mathrm{OPT}_{1,k,T'}\in\underset{k-T^2\le s\le k,\ T''\le T'}{\arg\max}\left\{w\left(\mathrm{OPT}_{1,s-1,T'-T''}\cup\mathrm{OPT}_{s,k,T''}\right)\right\}. \tag*{(3)}

First, notice that OPT1,s−1,T′−T′′∪OPTs,k,T′′\mathrm{OPT}_{1,s-1,T'-T''}\cup\mathrm{OPT}_{s,k,T''} is always obtainable by Lemma 14. Trivially, we have OPT1,1,T′=∅\mathrm{OPT}_{1,1,T'}=\varnothing since the block B1,1B_{1,1} is empty. For k>1k>1, if there is no edge (vi,vk)(v_i,v_k) in OPT1,k,T′\mathrm{OPT}_{1,k,T'}, we have w(OPT1,k,T′)=w(OPT1,k−1,T′)=w(OPT1,k−1,T′∪OPTk,k,0)w(\mathrm{OPT}_{1,k,T'})=w(\mathrm{OPT}_{1,k-1,T'})=w(\mathrm{OPT}_{1,k-1,T'}\cup\mathrm{OPT}_{k,k,0}). Otherwise, there is a family of boxes B\mathcal{B} with the properties in Lemma 14. In particular, since there is an edge (vi,vk)(v_i,v_k) in OPT1,k,T′\mathrm{OPT}_{1,k,T'}, there is one block Bs,kB_{s,k} in B\mathcal{B} with s≥k−T2s\ge k-T^2. Let T′′=τ(OPT1,k,T′∩Bs,k)T''=\tau(\mathrm{OPT}_{1,k,T'}\cap B_{s,k}). By induction and maximality of OPT1,k,T′\mathrm{OPT}_{1,k,T'},

w(OPT1,k,T′)=w(OPT1,k,T′∩Bs,k)+w(OPT1,k,T′∩B1,s−1)≤w(OPTs,k,T′′)+w(OPT1,s−1,T′−T′′)≤w(OPT1,k,T′),\begin{aligned} w(\mathrm{OPT}_{1,k,T'})=w(\mathrm{OPT}_{1,k,T'}\cap B_{s,k})+w(\mathrm{OPT}_{1,k,T'}\cap B_{1,s-1}) \\ &\le w(\mathrm{OPT}_{s,k,T''})+w(\mathrm{OPT}_{1,s-1,T'-T''}) \\ &\le w(\mathrm{OPT}_{1,k,T'}), \end{aligned}

so all the inequalities are tight and (3) is correct. For every k∈[n]k\in[n], T′∈[T]T'\in[T], there are at most T′⋅T2≤T′T'\cdot T^2\le T' choices of the last block Bs,kB_{s,k}, and OPTs,k,T′′\mathrm{OPT}_{s,k,T''} can be found by enumeration in time 2O(T′log⁡T)nO(1)2^{O(T'\log T)}n^{O(1)}. Since we need to compute nTnT values of FF, we end up with a total running time 2O(T′log⁡T)nO(1)2^{O(T'\log T)}n^{O(1)}.

References

  1. [1]Alfred V. Aho, Michael R Garey, and Jeffrey D. Ullman. The transitive reduction of a directed graph. SIAM Journal on Computing, 1(2):131–137, 1972.DOI
  2. [3]Jørgen Bang-Jensen and Gregory Z Gutin. Digraphs: theory, algorithms and applications. Springer Science & Business Media, 2008.
  3. [4]Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015.DOI
  4. [5]Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471–500, 2004.DOI
  5. [7]Benedikt Finnah, Jochen Gönsch, and Alena Otto. Overcoming poor data quality: Optimizing validation of precedence relation data. European Journal of Operational Research, 322(3):740–752, 2025.DOI
  6. [9]Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427–486, 2011.arxiv.org/abs/1003.3967
  7. [10]Gramoz Goranci, Adam Karczmarz, Ali Momeni, and Nikos Parotsidis. Fully dynamic algorithms for transitive reduction. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), pages 92:1–92:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025.arxiv.org/abs/2504.18161
  8. [11]Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In International conference on integer programming and combinatorial optimization, pages 205–216. Springer, 2013.
  9. [13]Pasin Manurangsi. Almost-polynomial ratio almost-ETH-hardness of approximating densest k-subgraph. Electronic Colloquium on Computational Complexity (ECCC), TR16(195), 2026.
  10. [14]Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The strongish planted clique hypothesis and its consequences. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), pages 10–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021.arxiv.org/abs/2011.05555
  11. [15]Silvano Martello and Paolo Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990.DOI
  12. [16]Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press, 2017.
  13. [17]Christian Otto and Alena Otto. Multiple-source learning precedence graph concept for the automotive industry. European Journal of Operational Research, 234(1):253–265, 2014.DOI
  14. [18]James B Orlin. Max flows in O(nm) time, or better. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 765–774, 2013.DOI
  15. [20]Sahil Singla. The price of information in combinatorial optimization. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, page 2523–2532. Society for Industrial and Applied Mathematics, 2018.arxiv.org/abs/1711.00405
  16. [22]Lihui Wang, Shadi Keshavarzmanesh, Hsi-Yung Feng, and Ralph O Buchal. Assembly process planning and its future in collaborative manufacturing: a review. The International Journal of Advanced Manufacturing Technology, 41(1):132–144, 2009.DOI

Paper details

vlnc:W_zfcbeefu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents