2
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ – Dmitry Oct 24 '20 at 13:54
  • $\begingroup$ I don't understand your algorithm for problem 1. What do you do for $\alpha_2$? $\endgroup$ – D.W. Oct 24 '20 at 20:01
  • $\begingroup$ @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$. $\endgroup$ – Joppy Oct 24 '20 at 22:49
  • $\begingroup$ @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. $\endgroup$ – Joppy Oct 24 '20 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.