*Left panel:* Illustration of the dynamic programming algorithm for computing the generating function of graph *G* shown in (*A*). The nodes of the *dynamic programming (DP) graph* (*B*) are defined as pairs (*v*,*x*), where *v* is a vertex of *G* and *x* is a score. Two nodes (*v*,*x*) and (*v*′,*x*′) are connected by an edge if and only if there exists an edge between vertices *v* and *v*′ in *G* with score *x*′-*x*. The probability of an edge between (*v*,*x*) and (*v*′,*x*′) in the DP graph equals to the probability of the edge (*v*,*v*′) in *G*. A source *s* in graph *G* corresponds to a single node (*s*,0) in the DP graph. A node (*v*,*x*) is present in the DP graph if and only if there exist a path from (*s*,0) to (*v*,*x*). In this example, red (blue) edges of the DP graph in (*B*) are from the red (blue) edges of the graph *G* in (*A*). All edge probabilities in (*B*) are 0.5 as the probabilities of edges of *G* are 0.5. The *node probability* of node (*v*,*x*) (shown inside nodes in (*B*) and (*C*)) is the total probability of the paths from the source *s* to *v* with the score *x*. The node probability of the source of the DP graph is initialized by 1, and the node probability of a node (*v*,*x*) is obtained by the *weighted* summation of the node probabilities of its *predecessors* (see ()). The generating function is represented by the probabilities of the sink nodes in the DP graph. To find all paths of score *x* from the source to the sink in graph *G* one has to backtrack all paths from the node (*t*,*x*) in the DP graph. For example, if *x* = 2, two such paths are found: {*s*, *v*_{2}, *v*_{4}, *v*_{7}, *t*} and {*s*, *v*_{3}, *v*_{6}, *t*} as in (*C*). *Right panel:* Path Dictionary and Gapped Path Dictionary. (*A*) *PD*(*G*,1) and the generating function of *G*. (*B*) The construction of *G*_{H} using edges between hubs *v*^{2} and *t* (shown as solid blue and red edges) as examples. Solid blue and red edges in *G*_{H} are induced by dashed blue and red paths in *G*. All paths that use only nonhub vertices in *G* are collapsed into edges in *G*_{H}. (*C*) The hub graph *G*_{H}, *GPD*(*G*,*H*,1), and the generating function of *G*_{H}.