Dijkstra with bitwise OR of edge costs

Question

Given a graph $G$ where loops and multiple edges are allowed. A path {$e_1, e_2, ..., e_k$} (a sequence of edges) has a cost $$ cost = e_1 | e_2 |...|e_k$$ where $|$ is the bitwise OR.

Assume for all edges in $G$, $e_i \ge 0$.

Now, the triangle inequality is satisfied, for this definition of cost. Meaning, as the path size increases, the path cost can never decrease.

So theoretically, to find the shortest between two vertices, Dijkstra's algorithm should give the right answer?

Answer 1

I'm not sure if you can adapt Dijkstra specifically in any way to this problem, but there's a different efficient solution that's actually easier to come up with.

Because bitwise operators treat bits independently, you can try to fix each bit in your answer, iteratively, from highest to lowest. The first question is "can I not have the highest bit set to 1 in my answer?". If after removing all edges with the highest bit set to 1 from the graph, the source and destination are still connected, the answer is yes, you throw away all those edges for good and proceed with the next bit. If the answer is no, you put the removed edges back, because they might come in handy, and again proceed with the next bit.

Running time is $O(Elog MaxCost)$.

Answer 2

Nice question indeed! Very interesting!!

First, let me please summarize my understanding of your problem:

Definition Let $\omega(\pi)$ denote the cost of a path $\pi\langle n_1, n_2, n_3, \ldots n_k\rangle$ which is defined as $c(n_1, n_2)|\omega(\pi')$, $\pi'$ is the suffix path $\langle n_2, n_3, \ldots, n_k\rangle$, $c(n_1,n_2)$ is the cost of the edge $\langle n_1, n_2\rangle$, and | is the bitwise or operator.

Goal To find a path $\pi^*$ from a source vertex $s$ to a target vertex $t$ such that $\omega(\pi^*)$ is minimized among all paths from $s$ to $t$.

Notice that $\omega(\cdot)$ is defined over the set of natural numbers $\mathbb{N}$. Indeed, if every vertex is characterized with $b$ bits, then the cost function takes values in the range $[0, 2^b-1]$.

Let me additionally highlight a couple of issues before going any further:

1. Your definition of triangle inequality is not very relevant to this case. Triangle inequality is used often in relation with the behaviour of heuristics. You might instead want to mean that costs grow monotonically and, as you are interested in minimizing the cost, this notion has been recently denoted as monotonicity of state spaces by Roni Stern et al.
2. A preferred way to verify theoretically whether Dijkstra/A$^*$ can be applied or not is to check if you are using a cost algebra or not as defined by Stefan Edelkamp et al..

Regarding the second point, if a cost distribution model satisfies a cost algebra then we know that Dijkstra/A$^*$ can be readily applied. This does not mean, however, that cost models which do not verify some properties of cost algebras can not be solved with the same algorithms ---or slightly modified versions of these algorithms.

Finally, note that you have not mentioned whether paths have to be simple or not so I will not address that issue here.

If my understanding is correct then, the cost of each edge is state-dependent: different paths to the same vertex have different costs, i.e. the cost of an edge is not a function of the out and in vertices connected through the edge (e.g., if vertices are locations over a map, then the edge cost is just the distance between them and this is a function just of the origin and target vertices of the edge), but a function of all states traversed before taking the edge!! This makes a huge difference with typical problems so that let me go deeper into this issue.

Consider the following simple digraph (i.e., no loops, no multiple edges are required to show the main difficulty in this problem):

where it is required to find the shortest path from 000 (in blue) to 100 (in red). Let us see how Dijkstra would work here:

1. s is expanded and $n_1$ and $n_2$ are inserted into OPEN in ascending order of their cost: $f(n_1)= 001 (1)$ whereas $f(n_2) = 110 (6)$, so that $n_1$ goes first and $n_2$ is inserted second. $n_1$ is inserted into CLOSED.
2. $n_1$ is expanded and $n_3$ is generated with a cost equal to $f (n_3) = 001 | 010 = 011 (3)$. Still, $n_2$ is second as $n_3$ is inserted before it. $n_1$ is inserted into CLOSED.
3. $n_3$ is expanded and the goal $t$ is generated with a cost equal to $f (t) = 011 | 100 = 111 (7)$. Hence, the goal is inserted into OPEN after $n_2$. $n_3$ is inserted into CLOSED
4. Now, $n_2$ is expanded and $n_3$ is generated with a cost equal to $f (n_3) = 110 | 010 = 110 (6)$ which is lower than the cost of the next node in OPEN (the goal, with a cost equal to 7). Hence, $n_3$ is re-inserted into OPEN with a cost equal to 6.
5. Phew! You might be thinking that $n_2$ gets a chance to discover a cheapest path to the goal. Unfortunately not!! Point is that $n_3$ is found in CLOSED and hence, it is immediately discarded!
6. The next node in OPEN is the goal with a cost equal to 7.

Dijkstra halts with the solution $\langle s, n_1, n_3, t\rangle$ which is incorrect as it has a cost equal to 7 units, whereas the path $\langle s, n_2, n_3, t\rangle$ has a lower cost, 6 units.

In the Figure above, thick vertices ($n_1$, $n_3$ and $t$) represent the problematic vertices: it can be easily verified that the bitwise OR of the involved costs equals 111 and, moreover, they are laid out in increasing order of cost so that there is no way for Dijkstra to foresee the trap until it is too late.

Fixing the problem does not seem easy. A simple way consists of getting rid of CLOSED and let Dijkstra just enumerate all paths in increasing order of their $f$-value. Note however that the number of paths can grow exponentially and hence this might be impractical. It is my feeling that there should be better ways than just running this modified version of Dijkstra.

Hope this helps,