Partial Path Interception in Derivation DAGs: Exact Reliability Laws and a Sharp Complexity Dichotomy
Abstract
Partial path interception (PPI) asks for a minimum-cost vertex set whose removal from a directed acyclic graph leaves at most a prescribed number of designated terminals able to reach a protected sink. We study how costs, depth, and fan-out affect its complexity. Unit-cost PPI is NP-complete at depth two with exactly two paths per terminal. Unique-path and individual-coverage instances admit polynomial-time algorithms, and bounded treewidth yields fixed-parameter tractability. Parameterized by the terminal threshold, weighted PPI is in XP and W-one-hard already at depth two, with no subexponential-time algorithm in that threshold under ETH. At depth two, undeletable terminals with bounded fan-out admit an FPT algorithm parameterized by the terminal threshold plus the fan-out bound. For unit costs, a dual-gammoid rank identity characterizes the optimum. Unit-cost depth-two instances with intermediate in-degree at most two are solvable in polynomial time for every terminal threshold, whereas depth-three instances are W-one-hard even with terminal out-degree one. On general directed acyclic graphs, minimum cuts and submodular optimization give a randomized approximation whose factor is the smaller of the coverage demand and roughly the square root of the number of initially exposed terminals, up to logarithmic factors. Reductions from smallest specified-edge subgraph, densest subgraph, and minimum union transfer conditional approximation lower bounds. PPI also gives an exact formulation of proof-valid caching under conjunctive derivation semantics: under independent premise erasures, the recovery probability equals one minus the erasure rate raised to the number of exposed premises. We extend this formulation to shared workloads, derive a sorting-based optimum under exact module routing, and give an AND-OR reliability envelope and a separate coded payload-recovery benchmark.
Related
- Joint optimization of detection, task allocation, and path planning for multi-agent cooperative interception under partial observability
- Borel complexity for product of trees and commuting partial maps
- Interception Conditions in Multi-Agent Pursuit Games Governed by Linear Dynamics with Gronwall-type Constraints
- Distributed Attacker Assignment and Interception Control in Multi-Agent Target-Attacker-Defender Games
- Constraint-Lifted Sector-Constrained Guidance for Rear-Approach Interception
BibTeX
@misc{xu2026partial,
title = {{Partial Path Interception in Derivation DAGs: Exact Reliability Laws and a Sharp Complexity Dichotomy}},
author = {Jianfeng Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.11782},
eprint = {2608.11782},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.11782},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Partial Path Interception in Derivation DAGs: Exact Reliability Laws and a Sharp Complexity Dichotomy
AU - Jianfeng Xu
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2608.11782
UR - https://arxiv.org/abs/2608.11782
AB - Partial path interception (PPI) asks for a minimum-cost vertex set whose removal from a directed acyclic graph leaves at most a prescribed number of designated terminals able to reach a protected sink. We study how costs, depth, and fan-out affect its complexity. Unit-cost PPI is NP-complete at depth two with exactly two paths per terminal. Unique-path and individual-coverage instances admit polynomial-time algorithms, and bounded treewidth yields fixed-parameter tractability. Parameterized by the terminal threshold, weighted PPI is in XP and W-one-hard already at depth two, with no subexponential-time algorithm in that threshold under ETH. At depth two, undeletable terminals with bounded fan-out admit an FPT algorithm parameterized by the terminal threshold plus the fan-out bound. For unit costs, a dual-gammoid rank identity characterizes the optimum. Unit-cost depth-two instances with intermediate in-degree at most two are solvable in polynomial time for every terminal threshold, whereas depth-three instances are W-one-hard even with terminal out-degree one. On general directed acyclic graphs, minimum cuts and submodular optimization give a randomized approximation whose factor is the smaller of the coverage demand and roughly the square root of the number of initially exposed terminals, up to logarithmic factors. Reductions from smallest specified-edge subgraph, densest subgraph, and minimum union transfer conditional approximation lower bounds. PPI also gives an exact formulation of proof-valid caching under conjunctive derivation semantics: under independent premise erasures, the recovery probability equals one minus the erasure rate raised to the number of exposed premises. We extend this formulation to shared workloads, derive a sorting-based optimum under exact module routing, and give an AND-OR reliability envelope and a separate coded payload-recovery benchmark.
ER -