Computing Longest Simple Path in a Particular Digraph

Question

Let $D$ be a digraph as follows:

I want to compute a longest simple path of it.

For an acyclic digraph, there is a method I can run in Python that returns a longest path, but $D$ is not acyclic.

I could try and compute all its simple paths and then calculate the longest one, but the digraph is too large for that to take a reasonable amount of time. So I was thinking on a different idea:

This digraph is very close to being acyclic; its only issue being the double arrows. Any simple path will traverse each double arrow at most once and thus in a single direction, so I can turn it into an acyclic digraph $D'$ by removing one direction of each double arrow of $D$ and compute a "long" simple path of $D$ by computing the longest path of $D'$ via the algorithm mentioned.

I got one of those by following that process. The computation time seems to be pretty fast too, which is good. The path:

[1-1, 1-2, 1-3, 1-4, 1-6, 1-8, 1-12, 1-13, 1-A3, 2-12, 2-13, 2-14, 2-15, 2-11, 2-B2, 3-4, 3-8, 3-9, 3-11, 3-D, 4-2, 4-9, 4-F, 5-1, 5-2, 5-3, 5-11, 5-10, 5-16, 5-17, 5-18, 5-25, 5-26, 5-I]

It's the green path, and it's not a longest one. I can alter it by going through the red or blue sections for longer paths.

So, to really compute a longest path an approach could be computing a longest path for each of its acyclic subgraphs, which is $2^{28}=268435456$ of them. Taking into account that the computations for each seem to be fast it may be computationally doable. Alternatively, I could compute longest paths for each zone starting in each leftmost vertex (and 2-2 and 3-13) and ending in each rightmost vertex. It looks like a lot less calculations so it may be a better one.

Is there an approach for this case that is even better than that? Like considering the graph is planar or something else.

Edit: Another idea. The digraph has different levels (like, Zone 1 has 5 levels): A total of 21 levels. You cannot decrease levels, so you can only stay in a level or go to a larger level. You usually just go to the next level, excluding the ?1, ?2 and ?3 vertices that allow you to skip ones. So for a long path you want to go through level-preserving arrows as much as possible and you want to avoid as many of the the ?1, ?2, ?3 vertices as possible.

Answer 1

The algorithm you mentioned allows you to assign weights to the edges, and can find the maximum weight path. You can modify your directed graph to get an acyclic directed weighted graph, such that the largest-weight path for the latter gives a longest path for the former.

Here is how you do the modification. For each pair of vertices $v_1$ and $v_2$ connected by a two-way edge, do the following:

• Delete the two-way edge connecting $v_1$ and $v_2$.

• For each vertex $w$ such that $w\to v_1$ but $w\not\to v_2$, add an edge with weight two $w\implies v_2$. We need to do this because it was possible to move from $w$ to $v_2$ in the original graph in two steps using the removed two-way edge.

• For each vertex $w$ such that $w\not\to v_1$ but $w\to v_1$, add an edge with weight two $w\implies v_1$.

• For each vertex $u$ such that $ v_1\to u$ but $ v_2\not\to u$, add an edge with weight two $v_2\implies u$.

• For each vertex $u$ such that $ v_1\not\to u$ but $ v_2\to u$, add an edge with weight two $v_1\implies u$.

Since no two-way edges remain, the new graph is acyclic. The added edges with weight two ensure the graph has the same paths as before. Therefore, you can use the weighted acyclic algorithm, and get a solution to the original problem.

For example, in Zone 1, looking at the two-way edge between vertices 4 and 6, you would make the following modifications:

• Delete the $4\longleftrightarrow6$ edge.

• Add in the weight two edges $3\implies 6$, $4\implies 10$, $4\implies 12$, $6\implies 9$.

Answer 2

The green path in the picture, with the modifications in red, is a longest path.

The digraph has 21 levels. Excluding four edges (That I'll call leaping edges), every edge either increases the level by 1, or it doesn't increase it at all. An ideal situation would be a path that doesn't use any of the four edges and uses the nonincreasing edges as much as possible.

• The path in green, and its modifications, don't use the four "leaping" edges. That's evident.
• The modifications of the path in green use as many nonincreasing edges as possible.

To prove the second point, first consider Zone 1. The path goes through a nonincreasing edge four times. The theoretical maximum would be seven, but:

• If you go through $8\leftrightarrow 14$ you cannot go through $12\leftrightarrow 13$.
• If you go through $10\leftrightarrow 9$ and $9\leftrightarrow 11$ you can neither go through $6\leftrightarrow 8$ and $8\leftrightarrow 14$, nor $6\leftrightarrow 8$ and $12\leftrightarrow 13$.
• If you go through $6\leftrightarrow 8$ and $12\leftrightarrow 13$ you cannot go through $6\leftrightarrow 8$ and $8\leftrightarrow 14$, or $10\leftrightarrow9$ and $9\leftrightarrow 11$.

All that means in Zone 1 you cannot use more than four nonincreasing edges, since you can use $1\leftrightarrow 2$ and $4\leftrightarrow 6$ "for free".

Now, in Zone 2 something similar happens. The arrows $13\leftrightarrow 14$ and $15\to11$ cannot be accessed at the same time as $6\leftrightarrow 10$ and $7\leftrightarrow 8$.

In Zone 3 you can go through $8\to 9$ and then to $12\to 13$ but that doesn't lead to a longest path. There is potential for this to increase the length of the path in 1 with respect to the alternatives but you lose in the long term.

In Zone 4 you can go through $1\leftrightarrow 2$, $10\leftrightarrow 11$, $6\leftrightarrow 7$ or $13\leftrightarrow 14$, but not any combination of two of them. So if you get to use one of those edges you can't lengthen your path any further in this zone.

Zone 5 is separated in two sections, one of which can only be accessed by going through $F$ and the other one by going through $G$ or $H$. In the second area you can go theoretically through a maximum of six nonincreasing edges (In reality only four), but the modified path goes through seven nonincreasing edges in the first area, which is the maximum, since you cannot go through $9\to 10$ and $11\to 10$ at the same time.

Therefore that path is a longest path.

With such argument not only you can verify that it's a longest path, but compute any longest paths of this digraph, manually, without using a computer.

It also works for shortest paths between $1$ in Zone 1 and $I$, $J1$ and $J2$ in Zone 5. In this case the shortest number of vertices without using leaping edges is 21, 1 per each level. With Djikstra you get a path of length 20 to $I$, a path of length 19 to $J1$ and a path of length 18 to $J2$. Instead, you can do as follows:

You're not forced to use a nonincreasing edge unless you want to go through the first leaping edge. Therefore the first leaping edge is optional. The second leaping edge skips two levels but unless you use a nonincreasing edge, you can only use it to get to $J1$ or $J2$. The third leaping edge only allows you to get to $I$. Last, the fourth leaping edge only allows you to get to $J2$. Any path without nonincreasing edges that goes through one of those (second, third or fourth) leaping edges is a shortest path.