1
$\begingroup$

I have a problem similar to Shortest path problem where edge weight depends on path taken but not quite the same. In my case each edge has either a fixed finite weight, or an infinite weight, depending on which path has been followed. So depending on the path taken through the graph, some edges from the current node are not allowed while others are. My graph is a DAG otherwise.

The shortest path can consist of many edges so I can't really represent the path history in the graph by duplicating nodes otherwise the number of nodes would increase exponentially and would be intractable.

Would Dijkstra's algorithm for finding the shortest path between two nodes still produce the correct answer in this particular type of graph? What else can I do?

$\endgroup$
1
$\begingroup$

The decision version of the problem you describe seems to be coNP-complete (assuming that the weight function description is polynomial in the size of the description of the graph).

The language corresponding to the decision version would be $L=\{G,w,s,t,p : p \text{ is the shortest path in G between s and t according to } w\}$

Lets take the complement of the language Hamilton Cycle, denoted by $\overline{HC}=\{G\big| \text{There is no hamiltonian cycle in G}\}$ (hamiltonian cycle is a cycle that visit every vertex of G exactly once).

It is well known that $\overline{HC}$ is coNP-complete.

Now we can reduce $\overline{HC}$ to $L$ (in polynomial time):

On input graph $G$:

  • Take an arbitrary vertex $u$, split it into two $u_{start}$, $u_{end}$ and connect them to all neighbors of $u$.
  • Create a weight function w in which all edges connected to $u_{end}$ has $\infty$ weight unless the path we have followed visits each vertex in $V \setminus \{u_{end}\}$ exactly once, and all other edges has weight 1 (this condition can be checked by a "short code" therefore $|w|$ is polynomial).
  • Add an edge $e'$ between $u_{start}$ and $u_{end}$ with a constant weight of $n+1$.
  • Output $(G,w,u_{start},u_{end},p)$ where $p$ is the path $u_{start} \underset{e'}{-}v_{end}$

The reduction is polynomial, and observe that there is no Hamiltonian cycle in $G$ if and only if $u_{start} \underset{e'}{-}v_{end}$ is the shortest path in $G$ between $u_{start}$ and $u_{end}$.

So there is no polynomial algorithm for your problem (unless P=NP).

$\endgroup$

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.