2
$\begingroup$

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges is $m=O(n)$. From every vertex, the one outgoing edge is already labelled as "type A" (a, in short) and the other one as "type B" (b, in short).

Considering that all edges have the same cost of 1, and that the type of edge is important for the path, I would like to find the shortest path from a specific vertex $u_1$ to some vertex of the set $\{v_1, ..., v_k \}$ (it is not specified which one, let's say that in the output of the algorithm it is $v_i$), such that if the same type of edges in that path is followed beginning from a specific vertex $u_2$, then that second path would also conclude to some vertex $v_j$ of the aforementioned set $\{v_1, ..., v_k \}$. This means that in some instance it could possibly hold that $i\neq j$, or in some other $i=j$.

The output of the algorithm it would be nice to have, therefore, can be said to be the sequence of edge types of path (e.g.: aababb), and the vertices $v_i$ and $v_j$. The input, of course, is the graph, the vertices $u_1$ and $u_2$, and the set of vertices $\{v_1, ..., v_k \}$.

There can be many solutions to this problem, so let's say we would want the one giving the lexicographically smallest sequence of edge types (i.e. $abab < abba$) on the paths.

Currently, what I have thought of is a version of two simultaneous BFS traversals, from $u_1$ and $u_2$ correspondingly, each with its own queue and parent-set, by following the same types of edges on each step (the lexicographical ordering on ties would be guaranteed by first queuing the vertices from a-edges and then from b-edges) and by considering "visited" every pair of vertices (i.e. $w$ "visited" = $w$ visited from $u_1$ and $w$ visited from $u_2$ = parent-set entries for $w$ exist for both two tables of parents) that have already been explored (because it wouldn't be correct to consider as visited the nodes of each individual instance of the BFS, since this path from $u_1$ possibly couldn't in some instance guarantee that when the same edge types are followed from $u_2$ it would lead to some $v_j\in\{v_1, ..., v_k \}$). This algorithm has a time complexity of $O((m+n)^2)=O(n^2)$, since $m=O(n)$.

Is there anything faster that can be applied here, considering (if it would be of any importance to the algorithm) that I can determine the adjacency of two vertices and the neighbours of a vertex in $O(1)$? Maybe using dynamic programming, or another graph algorithm modification that could make this faster than $O(n^2)$ in time complexity?

$\endgroup$
  • $\begingroup$ I think you probably only want to use lexicographical order to distinguish paths of the same length -- since $aaa$ is lexicographically less than the short path $bb$. $\endgroup$ – j_random_hacker Aug 3 at 18:38
  • $\begingroup$ Conceptually what you need to do is ordinary BFS -- but on a graph that has a vertex for every pair of vertices in the original graph. You start from the vertex $(v_1, v_2)$ in this graph, and BFS until you hit a goal vertex(-pair), that being any vertex $(a, b)$ such that $\{a,b\} \subseteq \{v_1, \dots, v_k\}$. This will be $O(n^2)$-time in the worst case, and I don't see how you could speed that up. Mind you, if the shortest-path distance is $d$, BFS will only explore the vertex(-pairs) in a radius-$d$ ball around the start vertex, which will be fast if you know $d$ is small. $\endgroup$ – j_random_hacker Aug 3 at 18:43
  • $\begingroup$ @j_random_hacker Yes, that's right, for the same length paths I meant to use the lexigraphical order. So, what you are proposing still is $O(n^2)$, worst-case, for example when there is no such path to be found, i.e. the goal-vertex-pair is unreachable from the starting vertex-pair. Another idea I just now got would be something similar to Dijkstra's method, i.e. starting from the end and somehow simultaneously trying to reach both of the "starting" vertices? Any ideas on that? $\endgroup$ – knehalem Aug 6 at 16: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.