5
$\begingroup$

The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.

Consider the following variant:

Find the two shortest paths between 2 pairs of arbitrary nodes, however the cost is considered to be the length of the path and in addition the number of nearby/common edges in the two paths. This cost is $|P_1| + |P_2| + |P_1 \cap P_2|$ when considering only common edges. More generally we can state the cost as $|P_1| + |P_2| + f(P_1, P_2)$ where it can generalize to consider both penalizing common edges or nearby edges.

Has this problem been addressed before?

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ The objective is not clear to me. Is the cost equal to the weight of the first plus the weight of the second path (so each common edge is counted twice) or is each common edge counted with higher weight, or something else? $\endgroup$
    – Sasho Nikolov
    Jul 19, 2015 at 4:17
  • $\begingroup$ It's probably fair to assume @chazisop's interpretation of the question, since the solution to the problem with objective function $|P_1| + |P_2|$ is trivial (take the shortest path twice). $\endgroup$
    – Sasho Nikolov
    Jul 20, 2015 at 15:11
  • $\begingroup$ @SashoNikolov The simplest cost is equal to each path cost plus their intersection $|P_1| + |P_2| + |P_1 \cap P_2|$ or more generally $|P_1| + |P_2| + f(P_1, P_2)$ $\endgroup$
    – Otto Nahmee
    Jul 20, 2015 at 19:27
  • 2
    $\begingroup$ Please edit the question to incorporate that in the question -- don't just leave clarifications in the comments. The question should stand on its own; people shouldn't have to read the comments. Are you assuming that every edge has length 1? $\endgroup$
    – D.W.
    Jul 21, 2015 at 6:33

2 Answers 2

Reset to default
7
$\begingroup$

If the cost is $|P_1|+|P_2|+|P_1∩P_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$ each of them with same edge weight as $e$. The shortest pair edge disjoint paths in the new graph corresponds to the required solution in the original graph.

The algorithm for shortest pair edge disjoint paths is known as Suurballe's algorithm.

https://en.m.wikipedia.org/wiki/Suurballe%27s_algorithm

If the cost is some arbitrary function the problem can be NP-complete. e.g assuming edge weights one, let the cost function be as $|P_1| + |P_2| + |P_1∩P_2| + 2\cdot |G-P_1\cup P_2|$. Then the cost is always $ \ge |G|+2$ (if source and terminal are distinct vertices). The equality holds iff the graph has a Hamiltonian cycle.

Improve this answer
$\endgroup$
-1
$\begingroup$

Let $P_{1}$, $P_{2}$ be two paths in a undirected unweighted graph $G=(V,E)$. We want to minimize the following quantity:

$ C = min_{P_{1},P_{2} \; paths \; in \; G} \{ |P_{1}| + |P_{2}| + |P_{1} \cap P_{2}| \}$.

Also suppose $L$ is the length of the shortest path in $G$, i.e. $L = min_{P \; path \; in \; G} \{ |P| \}$

Clearly, $2L \leq C \leq 3L$, since even if there is no overlap, the second shortest path cannot have length less than $L$ and in the worst case, we can pick two times the same path, which maximizes overlap.

This simple algorithm should solve your problem:

  1. Calculate the shortest path using your favourite algorithm.
  2. Subdivide all edges on the shortest path.
  3. Run your algorithm again on the new graph $G'$ and obtain a second path.
  4. Output the path from 1 and 3 as output, taking care to replace any subdivided edge in it with the original edge.

The running time is asymptotically the same for the usual algorithms,since $G'$ has at most $|E|+|V|$ edges and $|V|$ nodes and $|E|$ is almost always the dominating term of the runtime. This can be ignored however to always have the same running time (see below).

Correctness lies on the correctness of the original algorithm, as well as the fact that by subdividing we minimize according to the quantity $ |P_{2}| + |P_{1} \cap P_{2}| $, as desired.

Finally, note that most algorithms may work with weights from $\mathbb{N}$ with no additional cost, so instead of subdividing one may simply double the weight of the edges along the shortest path. This method is more general and shows that the algorithm works equally well on weighted variants of the problem.

Note that it is not necessary for the shortest path to be part of the optimal solution. See the comments for a discussion on this and thus why my proposed algorithm does not guarantee optimality.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Why is it optimal to choose the shortest path as $P_1$? It seems plausible that a different choice of $P_1$ makes it possible to make $|P_1| + |P_2| + |P_1 \cap P_2|$ smaller. $\endgroup$
    – Sasho Nikolov
    Jul 20, 2015 at 0:42
  • $\begingroup$ Here is a concrete counter-example along the lines proposed by Sasho Nikolov: The graph contains vertices s, x, y, and t, and five paths between these vertices. There are 2-edge paths s-x and y-t, 4-edge paths s-y and x-t, and a 1-edge x-y. The two paths should connect s to t. The optimal solution has two disjoint paths s-x-t and s-y-t of cost 6+6=12. The solution found by the above algorithm uses s-x-y-t of cost 5 and another path with total cost at least 13. $\endgroup$
    – Gamow
    Jul 20, 2015 at 7:51
  • $\begingroup$ You are correct, it is possible, I mistakenly assumed that the shortest path should always be one of the two. Basically, it suffices to satisfy the condition $|P \cap P_{1}| > |P_{1} \cap P_{2}| + |P_{2}| - |P|$, where $P_{1},P_{2}$ is the optimal solution, $P$ is the shortest path and wlog $|P \cap P_{1}| \leq |P \cap P_{2}|$, which one can easily satisfy with an "artificial" graph of paths. I will edit my answer. $\endgroup$
    – chazisop
    Jul 20, 2015 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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