2
$\begingroup$

Let $G=(V,E)$ be a directed graph, $\omega : E \rightarrow R$ a weight function, and $s,t \in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Moreover, 10 of its edges are colored in red (let's say that the rest are colored in blue).

I want to find an efficient algorithm that find the shortest path between $s$ and $t$ that goes through at least 5 different red edges.

Notice that going more than once through the same red edge is still considered as going through 1 red edge in the path.

One idea that I had was creating a graph $G'$ that will have a copy of every node for every possible set of red edges in $G$. That means that if we go through some red edge $e$, then the path will "move" to a variation of $G$ where $e$ is colored in blue and all the rest is the same.

However in this solution I will have to copy each node and each edge around 400 times. This will result in the same complexity asymptotically, but with such a big constant it seems really not efficient.

Another idea, was to somehow build the new graphs "on the run" of Bellman-Ford algorithm, but I don't really know how to do it.

I'll appreciate some help.

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ Has been asked before, I believe. $\endgroup$ – Yuval Filmus Dec 18 '18 at 5:28
  • 1
    $\begingroup$ Try using several different copies of $G$, arranged in layers. $\endgroup$ – Yuval Filmus Dec 18 '18 at 5:29
  • $\begingroup$ But isn't it result with too many copies of $G$? $\endgroup$ – Gabi G Dec 18 '18 at 6:58
  • $\begingroup$ Not at all. There are only a constant number of copies. $\endgroup$ – Yuval Filmus Dec 18 '18 at 8:02
  • $\begingroup$ Writing $R$ for the range of edge weights implies that negative edge weights are possible, which makes the problem NP-hard: If you have an algorithm that solves your problem, you can now also use it to solve Directed Hamiltonian Cycle on any graph by setting all of that graph's edge weights to -1, choosing some vertex $v$, adding a path of 4 red edges into $v$ and a single outgoing red edge from $v$. (The shortest 5-red-edge-containing path will necessarily involve a Hamiltonian cycle in the original graph, if this exists.) $\endgroup$ – j_random_hacker Dec 18 '18 at 12:49
4
$\begingroup$

What about reducing the problem first ?

UPDATED with more details :

  1. Build 2 node subsets:

    • Vs contains s and the 10 reached nodes of the red edges (called a1, a2, ..., a10 hereafter). This is a 11 nodes set.
    • Vt contains t and the 10 sources nodes of the red edges (called b1, b2, ..., b10 hereafter). This is another 11 nodes set.

  2. Build a distance matrix M from Vs to Vt (11x11)

  3. Do 11 Dijksta explorations, one starting from any node of Vs to reach all nodes of Vt. So you get 11 shortest distances to report in the matrix M. The diagonal terms are irrelevant (s->t or ak->bk).

  4. For each row of M, add wi (the weight of the red edge) to all elements (0 for s row). This is the price of crossing the red edge.

  5. Build an new graph G' with 11 nodes. node N0 for s&t and nodes Nk for each red edge (ak & bk). Then create all edges using matrix entry: w(Ni -> Nj) = M[i][j].

  6. Now your initial problem is equivalent to find a loop of 6 nodes containing N0 in G'. Use any method to test all combinatoric for instance Apass.Jack one. This step in NP complete.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Nice reduction and relaxation! $\endgroup$ – John L. Dec 18 '18 at 16:56
  • $\begingroup$ Could you elaborate? $\endgroup$ – Gabi G Dec 19 '18 at 10:50
  • $\begingroup$ @Gabi G, I precised the method ! Tell me if a point is missing. $\endgroup$ – Optidad Dec 19 '18 at 14:27
  • $\begingroup$ Dijkstra explorations may not be good enough because of the negative-weighted edges. $\endgroup$ – John L. Dec 20 '18 at 7:18
  • $\begingroup$ Well, just replace Dijkstra by Bellman-Ford if there is any. $\endgroup$ – Optidad Dec 20 '18 at 8:53
2
$\begingroup$

Here is the golden rule of dynamic programming. Adding another parameter to the subproblems/object function when there is an extra condition or dimension of freedom. In other words, when you cannot move from smaller subproblems to a larger subproblem because of a missing condition, add another parameter to represent that condition.

What is the extra condition here? At least 5 different red edges out of the given 10 edges have to be included in the path. Since there are 10 edges, we will add 10 parameters. Since each parameter has only two values, included or not_included, we can use one number to represent the value of those 10 parameters. That is, a number $0\le s\le 1023$, $$ s = s_0 + s_12+s_22^2+s_32^3+s_42^4+s_52^5+s_62^6+s_72^7+s_82^8+s_92^9$$ where $s_i=1$ if the path does include $i$-th red edge and $s_i=0$ otherwise.

What is the subproblem here? Find the length of shortest path with signature $s$ between two vertices, where $s=(s_0,s_1, \cdots, s_9)\in \{0,1\}^{10}$.

If there is no negative-weighted edges, a straightforward adaptation of Dijkstra's algorithm starting from $s$ will work for these subproblems. The answer will be the minimum among the shortest path with signature $a$ between $s$ and $t$ where at least 5 bits of $a$ are set to 1.

If there are negative-weighted edges, we will consider adapt the Floyd–Warshall algorithm. The details will not be included in this answer.

Note that the above suggestion only leads to the weight (length?) of shortest path. To find the actually path, we have to add another parameter to record the previous node that leads to the current shortest path of certain signature.

What Yuval suggested in his comment should be, I believe, essentially the same as what I have abstracted as the golden rule of dynamic programming. In fact, this answer is roughly to confirm the idea in the question, "creating a graph $G'$ that will have a copy of every node for every possible set of red edges in $G$". Hopefully the implementation here together with some bit twiddling might be easier and faster.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ It was essentially my idea too. But with this I will create almost 400 copies of $G$. Is it okay? $\endgroup$ – Gabi G Dec 18 '18 at 10:54
  • $\begingroup$ How many nodes are there? $\endgroup$ – John L. Dec 18 '18 at 14:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.