Directed Series-Parallel Graph (DSPG)
A DAG with unique source s and sink t reducible to a single edge via (i) series: remove degree-2 internal nodes; (ii) parallel: collapse multi-edges. Required structure for valid SL trust computation.
Parallel Non-intersecting Path Subnetwork (PNPS)
Pair (A,B) with ≥2 non-intersecting simple paths from A to B. A graph is not DSPG iff a PNPS has an intermediate node with an edge leaving or entering outside the PNPS.
Node Nesting Level (NNL) & nodeToPNPS
NNL(v) = number of PNPSs in which v is an intermediate node.
nodeToPNPS[v] = the most-nested PNPS in which v is intermediate. By Theorem 7: nodeToPNPS[a]=∅ or b∈nodeToPNPS[a] iff for every PNPS p containing a as intermediate, b is inside p. This allows O(1) criterion checks.
NNL(v) = |{PNPS p : v ∈ intermediates(p)}|
Synthesis criteria to admit branch A→B into G'
Original (Jøsang)
① Path A→B exists
② NNL(A) = NNL(B)
③ ∀ C intermediate: NNL(C) ≥ NNL(A)
Optimized (this paper)
① Path A→B exists
② |NNL(A)−NNL(B)| ≤ 1
③ ∀ C intermediate: NNL(C) ≥ max(NNL(A),NNL(B))
Implemented via NNL (recomputed) or nodeToPNPS (maintained incrementally — Algorithm 1 from the paper).
DSPG Analysis — two algorithms
Original (Jøsang): iterate over all PPSs; pick max-NL one; recompute edge NLs from scratch.
Optimized (nodeToPNPS): maintain nodeToPNPS after each reduction. Find innermost PNPS directly: the one whose intermediate nodes all point to it in nodeToPNPS — no full NL recompute needed. After removing internal nodes, just delete their entries from the map.