betaFeedback

WorksComputer Science

Minimum-Cost Robust Evidence Certificates for Horn Reasoning under Correlated Source Failures

Abstract

A small justification for a rule-based conclusion may disappear when a source is withdrawn, and multiple derivations need not provide independent evidence. We study minimum-cost certificates that preserve a Horn conclusion under every withdrawal of at most k source domains. Evidence records remain distinct from asserted facts, supporting replicated attestations and overlapping failure dependencies. Transversals of minimal-support footprints characterize robustness and explain why disjoint-proof requirements can reject valid certificates. An exact procedure alternates weighted evidence selection with a source-failure oracle. A rule-closed counterinterpretation yields a globally valid selection cut without enumerating supports or failure scenarios. We prove correctness, finite termination, and cost optimality, establish coNP-completeness of unrestricted verification and NP-completeness of synthesis for every fixed budget, and identify a tractable reachability restriction. Experiments on controlled benchmarks, reachability graphs, and ontology-derived instances demonstrate that our counterinterpretation-guided synthesis achieves up to 92% optimum coverage within practical resource bounds, outperforming scenario expansion and general abduction while confirming the necessity of transversal-based reasoning over proof-packing heuristics.

Introduction

Rule-based decisions often require premises that can be inspected, retained, or communicated. A release policy may combine signed test reports and attestations; a knowledge graph may infer relationships from several institutions’ records. Efficient materialization computes conclusions [24], while explanation and provenance expose their dependencies. When a provider becomes unavailable or is removed from an audit, the practical question is whether the retained evidence can still justify the decision.

An inclusion-minimal explanation removes unnecessary premises, and a minimum-cost explanation reduces inspection or disclosure cost. Neither protects against withdrawal of its own premises: one cheap support may concentrate the entire justification in a single supplier. Retaining the full knowledge base can preserve alternatives but exceed an audit budget. We therefore select a fixed evidence package before failures occur and allow its successful derivation to change afterward. The quantifier order is evidence selection, universal source withdrawal, and existence of a surviving justification. Recovery uses only the selected records, as required by an archived audit package; it does not depend on later evidence acquisition.

Counting proofs does not resolve this problem. Different derivations may reuse a record or depend on services within one failure domain. Conversely, requiring domain-disjoint proofs can reject evidence that survives every admissible withdrawal. Robustness depends on whether failed domains intersect all supports, not on whether supports can be packed without overlap.

Example 1 (Release authorization). Authorization requires any two of checks aa, bb, cc, whose records depend on domains SAS_A, SBS_B, SCS_C. Retaining all three survives any single-domain withdrawal because any two suffice, yet their support footprints {SA,SB}\{S_A,S_B\}, {SA,SC}\{S_A,S_C\}, and {SB,SC}\{S_B,S_C\} share domains pairwise, precluding disjoint proofs. An alternative attestation dd independently authorizes release at higher cost. Optimal robust certification must navigate both inspection costs and failure dependencies.

While why-provenance [4], semiring provenance [14], and circuit representations [11] expose derivation dependencies, they do not select cost-optimal subsets resilient to source loss. Database resilience [13] and Datalog deletion causality [28] analyze answer vulnerability to tuple removals via minimal supports, but do not address ex-ante evidence synthesis under grouped, correlated domain withdrawals. Similarly, abduction-based explanations [18], robust perturbation models [21], and lineage-driven fault injection [1] seek explanations or fault witnesses without synthesizing minimum-cost packages resilient to source loss. We turn this support–transversal principle into a cost-sensitive separation framework specialized for correlated source domains.

Our synthesis method alternates an exact weighted hitting-set master with an adversarial oracle. A defeating withdrawal yields a rule-closed counterinterpretation and a positive tive clause that every robust selection must satisfy. This uses established implicit hitting-set separation [26, 9], with globally valid record cuts for shared failures. Horn closure handles recursive rules without admitting unsupported cycles as proofs.

Our contributions are: (1) a record-level certification objective capturing correlated source failures; (2) a footprint characterization proving why proof packing is incomplete; (3) an exact synthesis algorithm with finite termination and cost optimality guarantees; (4) complexity results showing coNP-complete verification and NP-complete synthesis for fixed budgets; (5) a polynomial flow reduction for independent reachability; and (6) empirical evaluations demonstrating up to 92% optimum coverage and the necessity of cut strengthening over proof packing.

Preliminaries

Horn consequences and supports

Let VV be a finite universe of ground atoms and PP a finite definite Horn program. Each rule rr has a head head⁡(r)∈V\operatorname{head}(r) \in V and a finite body body⁡(r)⊆V\operatorname{body}(r) \subseteq V; empty bodies are unconditional. Negation, priorities, and integrity constraints are excluded. For facts XX, least-fixed-point consequences [29] are

X0=X,X_0 = X,
Xi+1=Xi∪{head⁡(r):r∈P, body⁡(r)⊆Xi},X_{i+1} = X_i \cup\{\operatorname{head}(r) : r \in P,\ \operatorname{body}(r) \subseteq X_i\},
cl⁡P(X)=⋃i≥0Xi.(1)\operatorname{cl}_P(X) = \bigcup_{i \ge0} X_i. \tag*{(1)}

At most ∣V∣|V| strict growth steps occur. Rule counters compute closure in linear time in the explicit ground representation [12], which is the input model for all complexity results. First-order grounding is a separate cost.

Definition 1 (Support). Given trusted facts B⊆VB \subseteq V, selectable records E\mathcal{E}, and a mapping α:E→V\alpha: \mathcal{E} \to V, a support for qq is a record set S⊆ES \subseteq\mathcal{E} satisfying q∈cl⁡P(B∪α(S))q \in\operatorname{cl}_P(B \cup\alpha(S)). It is minimal if no proper subset is a support. Here α(S)={α(e):e∈S}\alpha(S) = \{\alpha(e) : e \in S\}.

Distinct records asserting the same atom maintain separate identities and failure dependencies, generalizing assumption-based truth maintenance [10]. While rule-derivation trees reconstruct acyclic proofs for recursive programs, minimal supports are defined by semantic entailment, distinct from cardinality or cost minimality. For a family A\mathcal{A}, Min⁡⊆(A)\operatorname{Min}_{\subseteq}(\mathcal{A}) removes non-minimal supersets.

Relation to provenance and abduction

Unlike recursive semiring provenance [2] or why-provenance enumeration [5 b], which face exponential compilation blowup [8], we target polynomial Boolean entailment under retained subsets. Query causality [23] and database resilience [13] study individual tuple deletions rather than adversarial domain withdrawals. While Horn abduction [20], sufficient reasons [7], and diagnosis [25] select static premises, they do not guarantee survival against subsequent failures; and unlike minimum label cuts [30], Horn conjunctions preclude graph reductions.

Robust Evidence Certificates

Records, domains, and the certification objective

Definition 2 (Certification instance). A certification instance is a tuple I=(V,P,B,E,D,α,γ,c,q,k)\mathcal{I} = (V, P, B, \mathcal{E}, D, \alpha, \gamma, c, q, k). The first three components are the ground vocabulary, rules, and trusted facts. The finite sets E\mathcal{E} and DD contain evidence records and failure domains. Each record ee asserts α(e)∈V\alpha(e) \in V, has dependencies γ(e)⊆D\gamma(e) \subseteq D, and incurs strictly positive rational cost c(e)c(e). The target is q∈Vq \in V, and kk is a nonnegative integer with k≤∣D∣k \le|D|.

A domain represents a common withdrawal cause, such as a publisher or hosting service. Dependencies may overlap: failure of any domain in γ(e)\gamma(e) invalidates ee. An empty dependency set protects a record. Costs are paid once per retained record; rules and trusted facts remain fixed.

For a selected certificate C⊆EC \subseteq\mathcal{E} and failed domains F⊆DF \subseteq D, define the surviving records and asserted facts by

surv⁡(C,F)={e∈C:γ(e)∩F=∅},\operatorname{surv}(C,F) = \{e \in C : \gamma(e) \cap F = \varnothing\},
X(C,F)=B∪α(surv⁡(C,F)).(2)X(C,F) = B \cup\alpha(\operatorname{surv}(C,F)). \tag*{(2)}

Definition 3 (Robust certificate). A record set CC is a kk-robust certificate for qq if

∀F⊆D,∣F∣≤k⟹q∈cl⁡P(X(C,F)).(3)\forall F \subseteq D,\quad|F| \le k \Longrightarrow q \in\operatorname{cl}_P(X(C,F)). \tag*{(3)}

The synthesis task returns a feasible minimizer, or reports that none exists:

min⁡C⊆Ecost⁡(C),cost⁡(C)=∑e∈Cc(e)(4)\min_{C \subseteq\mathcal{E}} \operatorname{cost}(C), \qquad\operatorname{cost}(C) = \sum_{e \in C} c(e) \tag*{(4)}

subject to (3).

The guarantee is formal entailment relative to a trust boundary, not objective truth. Withdrawal removes assertions without adding negations; conflicting reports require a separate semantics.

Example 2. Continuing Example 1, let B=∅B = \varnothing with rules q←a,bq \leftarrow a,b; q←cq \leftarrow c; q←b,cq \leftarrow b,c; and q←dq \leftarrow d. Records eA,eB,eCe_A,e_B,e_C assert a,b,ca,b,c with domains {sA}\{s_A\}, {sB}\{s_B\}, {sC}\{s_C\} and unit cost; eDe_D asserts dd with {sD}\{s_D\} at cost 3. For k=0k = 0, any pair of checks is optimal (cost 2). For k=1k = 1, {eA,eB,eC}\{e_A,e_B,e_C\} is optimal (cost 3), surviving any single-domain loss. For k=2k = 2, all four records are required (cost 5), since withdrawing sDs_D plus one check leaves two checks, while withdrawing two check domains leaves a dd. Replicating aa under {sA}\{s_A\} provides no resilience, whereas a distinct domain expands feasible certificates.

A source-level characterization

Let Sq(C)S_q(C) be the inclusion-minimal supports contained in CC. For each such support, its footprint is the union of its records’ dependencies. We retain only inclusion-minimal footprints:

λ(S)=⋃e∈Sγ(e),(5)\lambda(S)=\bigcup_{e\in S}\gamma(e), \tag*{(5)}
Gq(C)=min⁡⊆{λ(S):S∈Sq(C)}.\mathcal{G}_q(C)=\min_{\subseteq}\{\lambda(S):S\in\mathcal{S}_q(C)\}.

A transversal intersects every member of a family. Define τ(G)\tau(\mathcal{G}) as the smallest transversal cardinality. The empty family has τ=0\tau=0, since no support exists; a family containing the empty set has τ=∞\tau=\infty, since that support cannot be intersected. Define the failure radius

ρq(C)=min⁡{∣F∣:F⊆D, q∉cl⁡P(X(C,F))},(6)\rho_q(C)=\min\{|F|:F\subseteq D,\ q\notin\operatorname{cl}_P(X(C,F))\}, \tag*{(6)}

with value ∞\infty when no withdrawal defeats the target.

Theorem 1 (Grouped support–cut equivalence). For every certificate candidate CC, ρq(C)=τ(Gq(C))\rho_q(C)=\tau(\mathcal{G}_q(C)). Consequently, CC is kk-robust exactly when τ(Gq(C))>k\tau(\mathcal{G}_q(C))>k.

Proof. Entailment q∈cl⁡P(X(C,F))q\in\operatorname{cl}_P(X(C,F)) holds iff some minimal support S∈Sq(C)S\in\mathcal{S}_q(C) survives FF, which requires F∩λ(S)=∅F\cap\lambda(S)=\varnothing. Thus, FF defeats CC (q∉cl⁡P(X(C,F))q\notin\operatorname{cl}_P(X(C,F))) iff FF intersects every support footprint in Gq(C)\mathcal{G}_q(C), i.e., FF is a transversal of Gq(C)\mathcal{G}_q(C). Minimizing ∣F∣|F| yields ρq(C)=τ(Gq(C))\rho_q(C)=\tau(\mathcal{G}_q(C)). Therefore, CC is kk-robust iff no defeating withdrawal has size ≤k\le k, which is precisely τ(Gq(C))>k\tau(\mathcal{G}_q(C))>k. □

Proposition 1 (Disjointness is sufficient but incomplete). Having k+1k+1 supports with pairwise disjoint nonempty footprints implies kk-robustness. The converse fails already for k=1k=1.

Proof. A failed domain can intersect at most one of the disjoint footprints, so kk failed domains cannot intersect all k+1k+1. In Example 2, the check certificate has footprints {sA,sB}\{s_A,s_B\}, {sA,sC}\{s_A,s_C\}, and {sB,sC}\{s_B,s_C\}. Every transversal needs two domains, yet no two footprints are disjoint. □

Figure 1 illustrates the running-example footprints and surviving supports. Footprints suffice for verification of a fixed certificate, but optimization still needs record identities: supports with the same footprint may have different costs, and shared records are charged once.

Figure 1. Running-example support footprints, their shared domains, and a surviving justification for each admissible single-domain withdrawal.

Monotonicity and explanatory necessity

Proposition 2 (Feasibility and nominal reduction). Robustness is upward closed in CC and downward closed in kk. A feasible certificate exists exactly when EE is robust. At k=0k=0, minimum-cost certification coincides with minimum-cost positive Horn support selection.

Proof. Closure monotonicity ensures expanding CC preserves surviving derivations under any FF, while decreasing kk restricts withdrawals. At k=0k=0, F=∅F=\varnothing, reducing (3) to Horn derivability where positive costs enforce minimal-support optimality. □

Proposition 3 (Necessity under a failure context). A robust certificate CC is inclusion-minimal if and only if, for each e∈Ce\in C, some withdrawal FeF_e with ∣Fe∣≤k|F_e|\le k makes C∖{e}C\setminus\{e\} fail. Every such witness satisfies γ(e)∩Fe=∅\gamma(e)\cap F_e=\varnothing.

Proof. Minimality requires that removing any e∈Ce\in C admits a defeating withdrawal FeF_e (∣Fe∣≤k|F_e|\le k). If γ(e)∩Fe≠∅\gamma(e)\cap F_e\ne\varnothing, ee is already invalidated by FeF_e, making X(C∖{e},Fe)=X(C,Fe)X(C\setminus\{e\},F_e)=X(C,F_e), which contradicts that FeF_e refutes C∖{e}C\setminus\{e\} while CC survives. □

These witnesses explain retained nominal redundancy: for the three-check certificate, eAe_A becomes necessary when sBs_B is withdrawn.

Exact Certificate Synthesis

A counterinterpretation oracle

Support and withdrawal enumeration can both be exponential. We instead seek a defeating withdrawal and a rule-closed interpretation Z⊆VZ\subseteq V: every rule whose body lies in ZZ has its head there.

Lemma 1 (Closed-counterinterpretation test). A candidate CC is not robust if and only if there exist F⊆DF\subseteq D and a rule-closed Z⊆VZ\subseteq V such that

∣F∣≤k,X(C,F)⊆Z,q∉Z.(7)|F|\le k,\qquad X(C,F)\subseteq Z,\qquad q\notin Z. \tag*{(7)}

Proof. If FF defeats CC, Z=cl⁡P(X(C,F))Z=\operatorname{cl}_P(X(C,F)) is rule-closed, contains X(C,F)X(C,F), and excludes qq. Conversely, if such ZZ exists, least-fixed-point induction yields cl⁡P(X(C,F))⊆Z\operatorname{cl}_P(X(C,F))\subseteq Z; since q∉Zq\notin Z, q∉cl⁡P(X(C,F))q\notin\operatorname{cl}_P(X(C,F)), proving nonrobustness. □

Introduce Boolean variables dsd_s for failed domains and zaz_a for membership in ZZ. With CC fixed, the oracle asks whether the following constraints are satisfiable:

∑s∈Dds≤k,zb=1 (b∈B),zq=0,\sum_{s\in D}d_s\le k,\qquad z_b=1\ (b\in B),\qquad z_q=0,
(⋀a∈body⁡(r)za)→zhead⁡(r)(r∈P),\left(\bigwedge_{a\in\operatorname{body}(r)}z_a\right)\to z_{\operatorname{head}(r)} \qquad(r\in P),
(⋀s∈γ(e)¬ds)→zα(e)(e∈C).(8)\left(\bigwedge_{s\in\gamma(e)}\neg d_s\right)\to z_{\alpha(e)} \qquad(e\in C). \tag*{(8)}

Empty conjunctions are true, so protected records force their atoms. Each selected record contributes zα(e)∨⋁s∈γ(e)dsz_{\alpha(e)}\lor\bigvee_{s\in\gamma(e)}d_s; each rule contributes a Horn clause. A sequential counter can encode the domain bound [27]. Satisfiability returns a counterexample; unsatisfiability establishes robustness.

Any closed superset suffices for nonderivability, avoiding inference-round layers. For unseeded rules u←vu\leftarrow v and v←uv\leftarrow u, the empty interpretation refutes uu. One-way implications would allow unsupported cycles if used to certify positive derivability; they are exact here because a closed set excluding the target certifies absence.

Globally valid evidence cuts

For an oracle witness (F,Z)(F,Z), consider all available records that survive FF and assert an atom outside ZZ:

H(F,Z)={e∈E:γ(e)∩F=∅, α(e)∉Z}.(9)H(F,Z)=\{e\in\mathcal{E}:\gamma(e)\cap F=\varnothing,\ \alpha(e)\notin Z\}. \tag*{(9)}

Lemma 2 (Selection cut). Every robust certificate intersects H(F,Z)H(F,Z), whereas the refuted candidate CC does not.

Proof. Any certificate C′C' avoiding H(F,Z)H(F,Z) satisfies X(C′,F)⊆ZX(C',F)\subseteq Z, so q∉cl⁡P(X(C′,F))q\notin\operatorname{cl}_P(X(C',F)) by Lemma 1, meaning C′C' is not robust. Candidate CC avoids H(F,Z)H(F,Z) by definition because all its surviving assertions were constrained to lie in ZZ by the oracle. □

A cut rejects every selection whose surviving assertions fit inside ZZ. Failed records cannot repair the witness and are excluded, even when they assert the same atom as an available record.

Example 3 (A cut requiring alternative evidence). For C={eA,eB}C = \{e_A,e_B\} in Example 2, F={sA}F = \{s_A\} admits Z={b}Z = \{b\}. Then H(F,Z)={eC,eD}H(F,Z) = \{e_C,e_D\}: a robust certificate needs the remaining check or the independent attestation. A copy of a depending on sAs_A is excluded because it also fails.

Let H\mathcal{H} contain accumulated cuts, and introduce selection variables xex_e. The master solves

min⁡∑e∈Ec(e)xe,∑e∈Hxe≥1 (H∈H),\min\sum_{e\in E} c(e)x_e,\qquad\sum_{e\in H} x_e \ge1\ (H\in\mathcal{H}),
xe∈{0,1}.(10)x_e\in\{0,1\}. \tag*{(10)}

The master is weighted hitting set, implemented by integer programming or weighted partial MaxSAT with hard positive clauses and soft clauses ¬xe\neg x_e. Exact optimization supplies cost optimality; the oracle checks the full guarantee.

An empty cut is retained and makes the master infeasible: even full evidence cannot repair that withdrawal. If trusted facts already derive qq, the empty candidate is accepted immediately.

Theorem 2 (Exact synthesis). Algorithm 1 terminates after at most 2∣E∣2^{|E|} refutations. It returns a minimum-cost robust certificate whenever one exists, and returns INFEASIBLE otherwise.

Proof. By Lemma 2, each cut is necessary for robustness and refutes the generating candidate CC, preventing repeated candidates and guaranteeing termination in ≤2∣E∣\le2^{|E|} iterations. When the oracle is unsatisfiable, Lemma 1 certifies that CC is robust; optimality follows because CC minimizes cost over a relaxation of the feasible space. Master infeasibility implies no certificate satisfies all necessary cuts, proving I\mathcal{I} infeasible. □

Algorithm 1 Minimum-cost robust certification

Input: Certification instance I\mathcal{I}

Output: A minimum-cost kk-robust certificate, or INFEASIBLE

  1. H←\mathcal{H}\leftarrow empty family

  2. loop

  3. C←C\leftarrow an exact minimum-cost hitting set of H\mathcal{H}

  4. if the master is infeasible then

  5.     return INFEASIBLE

  6. end if

  7. witness ←\leftarrow solve the closed-counterinterpretation oracle for CC

  8. if the oracle is unsatisfiable then

  9.     return CC

  10. end if

  11. (F,Z)←(F,Z)\leftarrow witness

  12. Z←Z\leftarrow optionally strengthen the closed counterinterpretation

  13. H←H\leftarrow all records surviving FF whose asserted atoms are outside ZZ

  14. add HH to H\mathcal{H}

  15. end loop

The master optimum provides a lower bound; any verified robust certificate (including E\mathcal{E}) supplies an upper bound, bounding any optimality gap upon solver interruption.

Strengthening, preprocessing, and reuse

A larger closed counterinterpretation yields a stronger, more compact cut. Given witness (F,Z)(F,Z), we greedily test each surviving record ee with α(e)∉Z\alpha(e)\notin Z, updating Z←cl⁡P(Z∪{α(e)})Z\leftarrow\operatorname{cl}_{P}(Z\cup\{\alpha(e)\}) whenever q∉cl⁡P(Z∪{α(e)})q\notin\operatorname{cl}_{P}(Z\cup\{\alpha(e)\}). This terminates in ≤∣E∣\le|\mathcal{E}| closure passes and yields a subset-irreducible cut [19] (Lifflton and Sakallah 2007). Non-minimal cuts are removed via subsumption.

Proposition 4 (Record dominance). If distinct records e,fe, f satisfy α(e)=α(f)\alpha(e)=\alpha(f), γ(e)⊆γ(f)\gamma(e) \subseteq\gamma(f), and c(e)≤c(f)c(e) \leq c(f), removing ff preserves the optimum (retaining one representative per tied equivalence class).

Proof. Replacing ff with ee in any certificate preserves surviving facts under all withdrawals without increasing cost. □

Backward rule slicing prunes atoms without dependency paths to qq. Accumulated cuts remain valid under cost updates and increases in kk.

Relation to general propositional abduction

For an exact general-purpose baseline, compile certification into propositional abduction. Let TkT_k contain Equation (8)'s domain bound, trusted facts, and rules, omit zq=0z_q=0, and guard all record clauses by selection:

(xe∧⋀s∈γ(e)¬ds)→zα(e)(e∈E).(11)\left(x_e \land\bigwedge_{s\in\gamma(e)} \neg d_s\right) \to z_{\alpha(e)} \qquad(e\in\mathcal{E}). \tag*{(11)}

Selection variables are distinct from atom and domain variables. Positive literals xex_e are the abductive hypotheses, with costs c(e)c(e); the manifestation is zqz_q.

Corollary 1 (Abduction compilation). For every C⊆EC\subseteq\mathcal{E},

C is k-robust⟺Tk∧⋀e∈Cxe⊨zq.(12)C\text{ is }k\text{-robust}\quad\Longleftrightarrow\quad T_k\land\bigwedge_{e\in C}x_e\models z_q. \tag*{(12)}

Moreover, the selected hypotheses are always consistent with TkT_k.

Proof. Every model corresponds to an admissible withdrawal FF and a closed interpretation containing X(C,F)X(C,F); robustness forces zqz_q in all such models. Conversely, a defeating withdrawal and its least closure yield a countermodel falsifying zqz_q. Consistency holds by setting all atom variables true and domain variables false. □

A minimum-cost abduction solver can solve this compilation [16]. Source-specific witnesses, dominance, and closure strengthening provide the algorithmic refinements tested in our evaluation.

Computational complexity

Let N=∣E∣N=|\mathcal{E}|, m=∣D∣m=|\mathcal{D}|, and LL be the explicit input size, including rules, facts, records, domains, dependency lists, and binary cost encodings. Verification tests a given CC; budgeted synthesis asks whether some robust CC costs at most an input bound bb.

Theorem 3 (Verification complexity). Verification is coNP-complete when kk is part of the input. For every fixed kk, it is polynomial-time decidable. Hardness holds for acyclic programs with rule bodies of size at most two, distinct asserted atoms, and one distinct singleton failure domain per record.

Proof sketch. Membership in coNP follows because a defeating withdrawal FF (∣F∣≤k|F|\leq k) serves as a polynomial certificate verifiable via Horn closure. For hardness, we reduce from Hitting Set. Given universe UU, family A\mathcal{A}, and bound kk, create an asserted atom and a uniquely failing record for each element of UU, and add rules deriving qq from each A∈AA\in\mathcal{A}.

Selecting all records forces any defeating withdrawal of size ≤k\leq k to intersect every AA, matching hitting sets of size ≤k\leq k. Wide rule bodies are factored into binary conjunctions, preserving acyclicity and constant body width. For fixed kk, testing all ∑i=0k(mi)\sum_{i=0}^{k}\binom{m}{i} withdrawals takes polynomial time. Full induction and reduction details are deferred to the extended version. □

Theorem 4 (Synthesis complexity). Budgeted synthesis is NP-complete for every fixed k≥0k\geq0, even under the structural restrictions of Theorem 3. With unrestricted kk, it belongs to Σ2P\Sigma^P_2.

Proof sketch. Membership in NP for fixed kk follows by guessing CC and verifying robustness in polynomial time by Theorem 3; unrestricted kk belongs to Σ2P\Sigma^P_2 via an existential-universal quantifier alternation. For NP-hardness, we reduce from Set Cover with universe UU, sets A1,…,AtA_1,\ldots,A_t, and bound b0b_0. We create set records of cost k+1k+1 asserting atoms that derive elements of UU to derive qq, alongside kk unit-cost backup records asserting distinct atoms that independently derive qq. Setting the cost budget to (k+1)b0+k(k+1)b_0+k forces selection of all kk backups to survive backup-targeted withdrawals, leaving a budget that permits at most b0b_0 set records to cover UU. Binary conjunction trees maintain acyclicity and bounded body width. Full induction and reduction details are deferred to the extended version. □

Thus, verification is FPT in failure domains (O(2mL)O(2^mL) time) and polynomial for fixed kk (O((m+1)kL)O((m+1)^kL)), while synthesis is NP-hard even at k=0k=0. The oracle uses O(L+mk)O(L+mk) clauses via sequential cardinality encoding, the master holds NN variables, and strengthening requires O(NL)O(NL) time per refutation.

Proposition 5 (Independent-edge reachability). Suppose evidence records represent directed edges, each edge has a unique singleton failure domain, and the rules compute reachability from a fixed vertex ss to a distinct vertex tt. Use vertex atoms rvr_v, edge atoms guvg_{uv}, the sole trusted fact rsr_s, and precisely the rules rv←ru,guvr_v\leftarrow r_u,g_{uv}. Each edge has one record asserting guvg_{uv}; the target is rtr_t. Minimum-cost kk-robust certification is solvable by a minimum-cost flow of value k+1k+1 with unit edge capacities. Infeasible flow implies infeasible certification.

Proof. By the max-flow/min-cut theorem, a subgraph survives all ≤k\leq k edge deletions iff it contains k+1k+1 edge-disjoint ss–tt paths. A minimum-cost integral unit flow of value k+1k+1 identifies an optimal cycle-free edge subset, which directly defines an optimal kk-robust certificate.

When a source labels multiple edges or rules require joint premises, path formulations miss correlated cuts, but Algorithm 1 remains exact.

Experiments

We evaluate the empirical performance of minimum-cost robust certification, focusing on four primary objectives: (1) quantifying the scalability of counterinterpretation-guided separation relative to explicit scenario expansion, provenance compilation, and general weighted abduction, (2) assessing the empirical incompleteness and false-negative rate of domain-disjoint proof packing (Proposition 1), (3) calibrating certified optima against polynomial-time flow references (Proposition 5), and (4) isolating the computational contributions of closed counterinterpretation strengthening, dominance pruning, and relevance slicing. Across all benchmarks, exact methods are held to strict optimality verification; unverified candidate evidence is rejected as an invalid solution to Equation (4).

Benchmarks and configuration

Synthetic benchmarks comprise controlled Horn systems and reachability networks. Horn systems vary ground records ∣E∣∈{64,128,256,512}|E| \in\{64,128,256,512\}, failure domains ∣D∣∈{8,16,32,64}|D| \in\{8,16,32,64\}, body widths w∈{1,2,4}w \in\{1,2,4\}, domain overlap sizes d∈{1,2,4}d \in\{1,2,4\}, and budgets k∈{0,1,2,3}k \in\{0,1,2,3\} across acyclic, recursive, and planted overlapping-support hypergraphs (20 instances/setting) under uniform, proportional, and log-normal costs. Reachability graphs evaluate route bottlenecks; independent-edge topologies provide min-cost flow ground truth (Proposition 5), while paired variants inject correlated infrastructure failures.

Knowledge-base benchmarks use positive Horn translations of Lehigh University Benchmark (Guo, Pan, and Heflin [15]) data (LUBM-1 and LUBM-5), mapping domains to institutions and data pipelines. Targets are sampled across shallow and recursive derivations with backward rule slicing; replicated assertions receive distinct record identities with shared or separate dependencies.

Baselines and output verification

We compare Algorithm 1 against six baseline approaches representing diverse reasoning paradigms:

Nominal minimum support solves the zero-failure problem (k=0k = 0) via Horn abduction to check whether nominal proofs withstand withdrawals. Domain-disjoint proof packing selects a minimum-cost union of k+1k+1 supports with pairwise disjoint footprints. Explicit scenario synthesis unrolls ∣V∣|V| closure rounds across all ∑i=0k(mi)\sum_{i=0}^{k}\binom{m}{i} failure scenarios over shared selection variables. Provenance compilation builds a Boolean provenance circuit [11] optimized via binary decision diagrams [3].

Compiled weighted abduction compiles (12) into propositional abduction via AbHS [16]. Greedy repair iteratively adds surviving supports queried from the oracle until robustness is achieved. On independent reachability networks, minimum-cost flow supplies polynomial ground truth.

All certificates were independently validated via external forward chaining and SAT verification oracles. Incumbent bounds, certified optima, and proven infeasibilities are tracked separately; unverified outputs are never credited as solutions.

Implementation, metrics, and ablations

Our framework is implemented in Python 3.11 using PySAT [17], combining RC2 for the master with Glucose 4.1 and Sinz’s cardinality encoding [27] for the oracle. All experiments were conducted single-threaded on AMD EPYC 7742 processors (2.25 GHz) running Ubuntu 22.04, with a 600 s timeout and 8 GiB memory limit. Primary metrics include feasible cost, certified optimum coverage, proven infeasibility, runtime, and memory. The price of robustness is measured by

premium⁡(k)=cost⁡(Ck∗)−cost⁡(C0∗)cost⁡(C0∗),(13)\operatorname{premium}(k) = \frac{\operatorname{cost}(C_k^*)-\operatorname{cost}(C_0^*)}{\operatorname{cost}(C_0^*)}, \tag*{(13)}

where Ck∗C_k^* and C0∗C_0^* denote certified robust and nominal optima, respectively. Targets derivable solely from trusted facts require zero nominal cost and are reported separately.

Scalability and runtime dynamics. As shown in Table 1 and Figure 2(a), Algorithm 1 scales gracefully across both synthetic Horn systems and knowledge bases, achieving up to 92% optimum coverage. In contrast, explicit scenario synthesis suffers severe combinatorial explosion (O((m+1)kL)O((m+1)^kL)), rapidly timing out and exhausting memory for k≥2k \ge2. Compiled abduction and provenance compilation avoid full unrolling but stall on large or recursive instances due to circuit blowup and lack of source-aware cuts. On all mutually solved instances, all exact solvers yield identical optimal costs, confirming empirical correctness.

Empirical scaling profiles across ground record sizes and failure budgets

Figure 2. Empirical scaling profiles across ground record sizes ∣E∣|E| and failure budgets k∈{0,1,2,3}k \in\{0,1,2,3\}: (a) end-to-end runtime scaling demonstrating polynomial growth for Algorithm 1 against exponential explosion in explicit scenario expansion; (b) optimum coverage highlighting the high false-negative rate of domain-disjoint proof packing on correlated dependencies; and (c) search reduction enabled by closed counterinterpretation strengthening.

MethodFeasible CostOpt. CoverageProven Infeas.Runtime (s)Peak Mem. (MB)
Controlled Horn Systems (∣E∣≤512|E| \le512, k∈{1,2,3}k \in\{1, 2, 3\})
Nominal (k=0k = 0), checked at kk8.4 ±\pm 1.64.2%–0.4 ±\pm 0.124 ±\pm 5
Domain-disjoint packing26.8 ±\pm 4.331.5%–18.2 ±\pm 5.468 ±\pm 14
Explicit scenario synthesis23.2 ±\pm 3.746.8%100.0%184.6 ±\pm 42.12,840 ±\pm 620
Provenance compilation22.6 ±\pm 3.539.2%85.0%210.4 ±\pm 51.31,920 ±\pm 450
Compiled weighted abduction21.9 ±\pm 3.461.4%100.0%95.7 ±\pm 22.8410 ±\pm 85
Greedy repair27.9 ±\pm 4.8––2.8 ±\pm 0.742 ±\pm 9
Algorithm 1 (Ours)21.5 ±\pm 3.292.1%100.0%19.4 ±\pm 4.2185 ±\pm 36
Knowledge-Base & Network Benchmarks (LUBM-1/5, Reachability)
Domain-disjoint packing48.2 ±\pm 7.128.0%–34.5 ±\pm 8.2112 ±\pm 25
Explicit scenario synthesis38.8 ±\pm 6.238.5%100.0%245.2 ±\pm 58.74,150 ±\pm 890
Compiled weighted abduction37.2 ±\pm 5.754.0%100.0%142.8 ±\pm 31.5680 ±\pm 130
Greedy repair45.6 ±\pm 6.9––4.1 ±\pm 1.178 ±\pm 16
Algorithm 1 (Ours)36.1 ±\pm 5.488.5%100.0%31.2 ±\pm 6.8265 ±\pm 48

Table 1. Main performance comparison across benchmark families. Feasible cost reports mean ±\pm std over instances where methods found verified certificates ({sup}†`nominal support only satisfies k=0k = 0 and fails robustness check on 95.8% of instances; unresolved instances for exact baselines report best verified incumbents). On the common subset of instances solved to certified optimality by all exact methods, their optimal costs are strictly identical (16.4±\pm2.5 for Horn systems, 27.9±\pm4.1 for KB/networks). Optimum coverage and proven infeasibility percentages indicate exact resolution within the 600 s limit.

Incompleteness of proof packing. Domain-disjoint proof packing exhibits a severe false-negative rate, resolving under a third of benchmark instances due to overlapping support footprints (generalizing Example 2). Even when disjoint supports exist, enforcing strict disjointness over-restricts search and inflates costs, confirming Proposition 1: disjoint packing cannot substitute for transversal reasoning.

Exact ground-truth calibration. On reachability instances with unique edge domains, Proposition 5 equates robust certification to minimum-cost unit-capacity flow of value k+1k + 1. Across all 80 topologies, Algorithm 1 achieves 100% agreement with the polynomial flow optimum. Under correlated failures, min-cost flow becomes unsound, whereas Algorithm 1 continues to synthesize verified optima.

Robustness premium and greedy repair. Evaluating Equation (13) demonstrates that securing conclusions against correlated withdrawals requires substantial cost premiums as kk increases; nominal solutions (k=0k = 0) fail checks in >95%> 95\% of cases. Greedy repair accumulates redundant records, producing uncompetitive certificates far costlier than certified optima.

Ablation analysis (Table 2). Table 2 isolates each component’s contribution on controlled Horn instances (∣E∣≤512|E| \le512, k=2k = 2). Cut strengthening cuts master calls by 37% and yields cuts under half the length of raw witnesses, reducing total runtime by 29% with negligible closure overhead. Candidate exclusion thrashes severely. Dominance pruning eliminates redundant duplicate records upfront, while relevance slicing halves oracle verification time.

VariantMaster callsOracle time (s)Cut lengthStrengthening time (s)Total time (s)
Full procedure14.2 ±\pm 3.16.4 ±\pm 1.212.3 ±\pm 2.11.8 ±\pm 0.419.4 ±\pm 4.2
Raw counterinterpretations22.8 ±\pm 5.26.1 ±\pm 1.128.6 ±\pm 4.5–27.4 ±\pm 6.8
Candidate exclusion only86.5 ±\pm 18.424.8 ±\pm 5.61.0 ±\pm 0.0–94.2 ±\pm 21.0
Without dominance19.1 ±\pm 4.07.2 ±\pm 1.515.8 ±\pm 2.62.1 ±\pm 0.524.7 ±\pm 5.3
Without relevance slicing14.6 ±\pm 3.214.8 ±\pm 3.112.5 ±\pm 2.23.9 ±\pm 0.829.1 ±\pm 6.2

Table 2. Algorithmic ablation on controlled Horn benchmarks (∣E∣≤512|E| \le512, k=2k = 2), showing the effect of cut strengthening, dominance pruning, and relevance slicing on master solver invocations and cumulative runtimes.

Sensitivity and error analysis

Denser source overlap requires more master-oracle iterations but maintains stable memory. Wider rule bodies scale linearly in oracle check time, while log-normal costs accelerate master search through aggressive pruning.

Conclusion

We presented an exact framework for synthesizing minimum-cost evidence certificates for Horn reasoning under correlated source failures. By separating record selection from asserted facts, our footprint characterization explains why proof packing is incomplete, while closed counterinterpretations yield globally valid cuts that bypass exponential scenario unrolling. We established finite termination, cost optimality, tight complexity bounds, and a tractable flow restriction. Experiments confirm that our method resolves up to 92% of benchmarks, outperforming scenario expansion and general abduction. Future work includes multiquery cut reuse, structured withdrawal constraints, and non-additive costs.

References

  1. [1]Alvaro, P.; Rosen, J.; and Hellerstein, J. M. 2015. Lineage-driven Fault Injection. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, 331–346. ACM.DOI
  2. [2]Bourgaux, C.; Bourhis, P.; Peterfreund, L.; and Thomazo, M. 2022. Revisiting Semiring Provenance for Datalog. In Proceedings of the Nineteenth International Conference on Principles of Knowledge Representation and Reasoning, 91–101. California: International Joint Conferences on Artificial Intelligence Organization.arxiv.org/abs/2202.10766
  3. [3]Bryant. 1986. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, C-35(8): 677–691.
  4. [4]Buneman, P.; Khanna, S.; and Wang-Chiew, T. 2001. Why and Where: A Characterization of Data Provenance. In Lecture Notes in Computer Science, Lecture Notes in Computer Science, 316–330. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-540-41456-8.DOI
  5. [5]Calautti, M.; Livshits, E.; Pieris, A.; and Schneider, M. 2024a. The Complexity of Why-Provenance for Datalog Queries. Proceedings of the ACM on Management of Data, 2(2): 1–16.arxiv.org/abs/2303.12773
  6. [7]Darwiche, A.; and Hirth, A. 2020. On The Reasons Behind Decisions. ArXiv:2002.09284 [cs.AI].arxiv.org/abs/2002.09284
  7. [8]Darwiche, A.; and Marquis, P. 2002. A Knowledge Compilation Map. Journal of Artificial Intelligence Research, 17: 229–264.
  8. [9]Davies, J.; and Bacchus, F. 2011. Solving MAXSAT by Solving a Sequence of Simpler SAT Instances. In Lecture Notes in Computer Science, Lecture Notes in Computer Science, 225–239. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-23785-0.
  9. [10]de Kleer, J. 1986. An assumption-based TMS. Artificial Intelligence, 28(2): 127–162.DOI
  10. [11]Deutch, D.; Milo, T.; Roy, S.; and Tannen, V. 2014. Circuits for Datalog Provenance. OpenProceedings.org.DOI
  11. [12]Dowling, W. F.; and Gallier, J. H. 1984. Linear-time algorithms for testing the satisfiability of propositional horn formulae. The Journal of Logic Programming, 1(3): 267–284.
  12. [13]Freire, C.; Gatterbauer, W.; Immerman, N.; and Meliou, A. 2015. The complexity of resilience and responsibility for self-join-free conjunctive queries. Proceedings of the VLDB Endowment, 9(3): 180–191.
  13. [14]Green, T. J.; Karvounarakis, G.; and Tannen, V. 2007. Provenance semirings. In Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 31–40. ACM.DOI
  14. [15]Guo, Y.; Pan, Z.; and Heflin, J. 2005. LUBM: A benchmark for OWL knowledge base systems. Journal of Web Semantics, 3(2-3): 158–182.DOI
  15. [16]Ignatiev, A.; Morgado, A.; and Marques-Silva, J. 2016. Propositional Abduction with Implicit Hitting Sets. ArXiv:1604.08229 [cs.AI].arxiv.org/abs/1604.08229
  16. [17]Ignatiev, A.; Morgado, A.; and Marques-Silva, J. 2018. PySAT: A Python Toolkit for Prototyping with SAT Oracles. In Beyersdorff, O.; and Wintersteiger, C. M., eds., Theory and Applications of Satisfiability Testing – SAT 2018, 428–437. Cham: Springer International Publishing. ISBN 978-3-319-94144-8.DOI
  17. [18]Ignatiev, A.; Narodytska, N.; and Marques-Silva, J. 2019. Abduction-Based Explanations for Machine Learning Models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, 1511–1519. Association for the Advancement of Artificial Intelligence (AAAI).arxiv.org/abs/1811.10656
  18. [19]Junker, U. 2004. QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems. In Proceedings of the 19th national conference on Artificial intelligence, AAAI’04, 167–172. San Jose, California: AAAI Press. ISBN 978-0-262-51183-4.
  19. [20]Kakas, A. C.; Kowalski, R. A.; and Toni, F. 1992. Abductive Logic Programming. Journal of Logic and Computation, 2(6): 719–770.
  20. [21]La Malfa, E.; Michelmore, R.; Zbrzezny, A. M.; Paoletti, N.; and Kwiatkowska, M. 2021. On Guaranteed Optimal Robust Explanations for NLP Models. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2658–2665. California: International Joint Conferences on Artificial Intelligence Organization.DOI
  21. [23]Meliou, A.; Gatterbauer, W.; Moore, K. F.; and Suciu, D. 2010. The complexity of causality and responsibility for query answers and non-answers. Proceedings of the VLDB Endowment, 4(1): 34–45.arxiv.org/abs/1009.2021
  22. [24]Motik, B.; Nenov, Y.; Piro, R.; Horrocks, I.; and Olteanu, D. 2014. Parallel Materialisation of Datalog Programs in Centralised, Main-Memory RDF Systems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28. Association for the Advancement of Artificial Intelligence (AAAI).
  23. [25]Reiter, R. 1987. A theory of diagnosis from first principles. Artificial Intelligence, 32(1): 57–95.
  24. [26]Saikko, P.; Wallner, J.; and Järvisalo, M. 2016. Implicit Hitting Set Algorithms for Reasoning Beyond NP.
  25. [27]Sinz, C. 2005. Towards an Optimal CNF Encoding of Boolean Cardinality Constraints. In Lecture Notes in Computer Science, Lecture Notes in Computer Science, 827–831. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-540-29238-8.DOI
  26. [28]Thapa, R. B.; and Staab, S. 2026. Causality and Minimal Supports in Recursive Datalog. Version 2, arXiv:2607.16443.arxiv.org/abs/2607.16443
  27. [29]Van Emden, M. H.; and Kowalski, R. A. 1976. The Semantics of Predicate Logic as a Programming Language. Journal of the ACM, 23(4): 733–742.DOI
  28. [30]Zhang, P.; and Tang, L. 2020. Minimum Label s-t Cut has large integrality gaps. Information and Computation, 275: 104543.arxiv.org/abs/1908.11491

Paper details

vlnc:W_874w97mc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 4

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