# Counting paths by their type

An edge-labelled directed graph is the data of $$G = (V, E, l)$$ where $$(V, E)$$ is a directed graph, and $$l \colon E \to \mathbb{P}$$ is some function. (For the graph I am considering, labels take values in $$\mathbb{P} = \{1, 2, 3, \ldots\}$$). To any path $$v_0 \to v_1 \to \ldots \to v_n$$ in $$G$$, we can associate a type $$\alpha = (\alpha_1, \ldots, \alpha_n) \in \mathbb{P}^n$$, where $$\alpha_i = l(v_{i-1}, v_i)$$. For a fixed source vertex $$s$$, destination vertex $$t$$, and type $$\alpha \in \mathbb{P}^n$$, let $$P(s, \alpha, t) \in \mathbb{N}$$ be the number of $$s \rightsquigarrow t$$ paths of type $$\alpha$$.

I have two counting problems, the first of which I can solve fairly efficiently, and the second of which I am hoping for some assistance. In the problem I am considering, the directed graph is acyclic, and satisfies other interesting properties: for example $$P(s, \alpha, t) = P(s, \beta, t)$$ whenever $$\alpha$$ is a permutation of $$\beta$$. Furthermore, in the problem I am consdiering $$G$$ is an infinite graph, but each of the following problems is finite.

Problem 1: Fix a source $$s \in V$$ and a type $$\alpha$$, and determine all of the numbers $$P(s, \alpha, -)$$.

Problem 2: Fix a source $$s \in V$$ and a destination $$t \in V$$, and determine all of the numbers $$P(s, -, t)$$.

For problem 1, we can take an approach very similar to counting paths in a DAG. Initialise an array $$\mathtt{D}$$ indexed by $$V$$ to zero, and set $$\mathtt{D}[s] = 1$$. Then perform a breadth-first search, at the first layer following all edges of type $$\alpha_1$$, and for each $$s \xrightarrow{\alpha_1} v$$ increment $$\mathtt{D}[v]$$ by $$\mathtt{D}[s]$$. Repeat for all the $$\alpha_2, \ldots, \alpha_n$$. At the end, the last layer contains all vertices $$t$$ reachable from $$s$$ via an $$\alpha$$-path, and $$\mathtt{D}[t]$$ is equal to $$P(s, \alpha, t)$$.

Problem 2 is more tricky, and the best strategy I have at the moment is essentially to iterate over the potential allowed types $$\alpha$$ and compute each $$P(s, \alpha, t)$$ individually. Another approach would be to do a breadth-first-search from $$s$$, but storing at each vertex the path type leading there, together with multiplicity - but this doesn't seem to be faster.

• What kind of efficiency are you looking for? It's easy to construct an acyclic graph where there are $O(2^{n/3})$ paths with different types (a concatenation of rhombuses), and therefore even outputting the answer is not efficient. – Dmitry Oct 24 '20 at 13:54
• I don't understand your algorithm for problem 1. What do you do for $\alpha_2$? – D.W. Oct 24 '20 at 20:01
• @D.W. Let the BFS layers be $L_0 = \{s\}, L_1, \ldots, L_n$, where $L_i$ is everything reachable from $L_{i-1}$ by following an edge labelled $\alpha_i$. Initially $\mathtt{D}[s] = 1$. For each vertex $v \in L_i$, set $\mathtt{D}[v] = \sum_{u \to v} \mathtt{D}[u]$, where the sum is taken over all $\alpha_i$-edges going from $L_{i-1}$ into $v$. Do this in ascending order of layers. At the end, $L_n$ contains precisely those $t$ with nonzero $P(s, \alpha, t)$, and $\mathtt{D}[t]$ contains the number of $\alpha$-paths $s \rightsquigarrow t$. – Joppy Oct 24 '20 at 22:49
• @Dmitry The actual problem I am trying to solve is NP-hard, so I am not expecting a terribly efficient solution, just something that is "fast enough" for my purposes. The graph is not too terrible - for example the symmetry property means that it is enough to consider only those path types $\alpha$ where $\alpha$ is in sorted order. – Joppy Oct 24 '20 at 22:54