12

It is NP-complete for directed graphs. Even deciding if there exist a path from $s$ to $t$ using vertex $u$ is NP-complete. The 2-node disjoint path problem is NP-hard for directed graphs$^1$. Given a directed graph $G$ and vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, does there exist two node disjoint paths that goes from $s_1$ to $t_1$ and $s_2$ to $...


11

Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through those vertices in the same order given by the topological order. So (since $s$ and $t$ must always be included) there are at most $2^{n-2}$ paths. This bound is ...


9

As Chao mentioned, the directed case is known to be NP-hard even for unweighted graphs. That said, the problem is fixed parameter tractable with respect to the path length. For undirected graphs, you can solve the weighted version of the problem, deterministically, in $O(|E|^2 \log|E|)$ using minimum cost flow.


9

The mistake is in This can only be true if there are no negative-weight cycles reachable from the source. Actually, this can only be true if there are no negative-weight edges reachable from the source. So the "double Dijkstra" suggested above may wrongly return false in a graph with negative-weight edges but no negative-weight cycles, whereas Bellman-...


8

We just answered this for $k=2$: Andreas Björklund and Thore Husfeldt, Shortest two disjoint paths in polynomial time, ICALP 2014, to appear. PDF of proceedings version, rev. e5d5661


8

This is known as the "time-dependent shortest path" problem. Indeed research has been done for this problem; see for example the classical paper by Orda and Rom, and this recent SODA paper which proves that when the weight function of each edge is polynomial-size piecewise-linear, then the shortest path between two fixed points changes $n^{\Theta(\log n)}$ ...


7

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. ...


6

This problem is well considered and learned in recent decades as every GPS device faces this problem. In practice (AFAIK), the standard way of facing this problem is by the usage of distance oracles, which usually (or more correctly, used to) approximate the distance between every two nodes by keeping only a $k\times n$ distances tables for a well-selected $...


6

Well, the problem is in $P$ after all. I'll keep the previous answer as it also works for the directed case (which is NPC, as answered on the other question), and shows it is $FPT$ with respect to $l$. In the undirected case, it is solvable, deterministically via minimum cost flow (this might not work on the scales you are referring to in the question, but ...


5

There are known pre-processing methods that rely solely on the graph representation itself (and not on any kind of geometric embedding) to establish good heuristics for A*. Perhaps the most well-known example in recent research is called ALT (A* + Landmarks + Triangle-Inequality). Here is one of the original papers on this topic: https://www.microsoft.com/en-...


4

For K=2, PARTITION reduces to this problem, so it is NP-hard. Take an instance of PARTITION: a list of nonnegative integers $x_1,\dots ,x_n$, and you ask if there is a subset $I\subseteq [1,n]$ such that $\sum_{i\in I} x_i=\sum_{i\notin I}x_i$. Let $S=\sum_{i\in[1,n]} x_i$, and $y_i=\exp(-\frac{x_i}S)$ for each $i$. Note that $y_i\in (0,1)$. You build a ...


4

Indeed: Eppstein has shown that the TSP can be solved in time $O(1.26^n)$ if all vertices are of degree at most 3. David Eppstein: The Traveling Salesman Problem for Cubic Graphs. J. Graph Algorithms Appl. 11(1): 61-81 (2007) Some tiny improvements of this result are also known, for instance by Liśkiewicz and Schuster (2014) to $O(1.255^n)$.


3

Considering your response in the comments where you do not necessarily need a provably-better runtime: Have a look at the three methods described in this tutorial: https://www.hackerearth.com/practice/algorithms/graphs/hamiltonian-path/tutorial/ Your DP model solution is option 2. With a sparse graph, a large number of subgraphs will not be connected and ...


3

There is a polynomial-time algorithm for this problem in the case where $C \le 2$. There is also a polynomial-time algorithm when $C > 2$, assuming paths are not required to be simple. If you require paths to be simple and have $C>2$, the problem is NP-hard, as explained by Neal Young. So in the remainder of this answer I will assume that either $C ...


3

Yen's original paper 1, from 1971, only establishes an upper bound of $O(Kn^4)$ operations (see Table 1). Lawler's original paper 2, from 1972, improves the time complexity upper bound to $O(Kn^3)$. Wikipedia's analysis of Yen's algorithm, leading to the $O(Kn(m+n\log n))=O(Kn^3)$ upper bound, is based on the Fibonacci heap implementation of Dijkstra's ...


3

EDIT (Jan 2019): Lemma 2 as currently stated below is wrong. (Indeed, given any instance, adding a single edge with a single type of very large cost will not change the instance but will yield $N(I)=1$, in which case the lemma claims that the algorithm will give an optimal solution. The proof is wrong because the function $\Phi$ defined there is not ...


3

If you are looking for a way to name (or alternately characterize) these edges you call "useless" and "necessary," you could refer to them as the edges with betweenness centrality =0 and =1, respectively. Every edge can be classified as having =0, =1 or in(0,1) betweenness measure in time of all-pairs-shortest-paths. This is a well-studied measure of ...


3

I have emailed the authors and they kindly supplied me with the following example: Let the nodes be contracted in alphabetical order then the red edge will be added during contraction. Now look at the upward search from A (i.e. we can only visit nodes that have been contracted later). A will settle B with distance 1 and D with distance 2. Since we are not ...


3

This may be related to network formation games - games in which players try to find a path in a network, and collaborating along a path reduces the cost for both players (i.e. the cost is shared) This paper may be of help.


3

Are you aware of the "shortest nondecreasing paths" problem? It was defined to model situations such as these. Although it's a bit less expressive compared to your formulation, there are fast algs for it.


3

No, Bellman-Ford won't work because the problem you described is NP-hard. This is pretty easy to prove. I've been able to come up with several reductions using the same strategy. The general idea is to make it so that in the path you have several sections that can be chosen independently; then the overall question becomes whether you can coordinate all ...


3

The longest path problem can be reduced to this problem. Let $G = (V,E)$ be an instance of longest $s,t$-path problem. For each vertex $v \in V$ create two vertices, $v_{in}$ and $v_{out}$, and a directed edge with weight $-1$ from $v_{in}$ to $v_{out}$. For each edge $(u, v) \in E$, create an edge from $u_{out}$ to $v_{in}$ with weight $0$. Now each trial ...


3

This answer doesn't answer the question about previous work, but it does show the problem is NP-complete. Lemma 1. Finding a shortest $s$-$t$ hyperpath (as defined in the post) in a given hypergraph is NP-complete, even in hypergraphs of hyperedge degree 3. Proof. Clearly the problem is in NP. It is NP-hard by the following reduction from 3D-matching. ...


2

I think the first proof was given in Der-Tsai's 1978 thesis on pages 111-113. With the above result it is immediate to realize that the shortest path problem with line segments as obstacles can be solved by first constructing the graph G=(V,E), called visibility graph, where V consists of the two distinguished points and the set of 2N endpoints of ...


2

It seems NP-complete even with weights in $\{0,1\}$. I reduce from the MINSAT problem: given a SAT instance, find an assignment that minimizes the number of satisfied clauses. More precisely, an instance is a CNF formula, and an integer $k$, and you have to say whether there is an assignment satisfying at most $k$ clauses. It is shown to be NP-complete in ...


2

In Victor Teixeira de Almeida, Ralf Hartmut Güting: Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases. SAC 2006: 58-62, Teixeira and Güting describe a new storage schema with a set of indexed structures to support an efficient execution of a slightly modified version of the Dijkstra's algorithm. In the ...


2

I think highway dimension is a formalization of a physical property for roadmaps. Assume that you have a large country. You want to get from one small city to another one. If the cities are far enough from each other, than you can assume that the route between them goes through one of the biggest city of the country. So it make a sense to add all large ...


1

There exists an optimal solution $p,q,c$ such that $c_e = l_e$ for all edges $e$ in the path $q$ and $c_e = u_e$ otherwise. For the optimal solution from point 1 exists a vertex $x$ at which the paths $p$ and $q$ split. The subpath $p^x$ of $p$ from $x$ to $v$ is a shortest path from $x$ to $v$ for the edge weights $u$ (the upper bound). To solve the ...


1

You can start by converting your graph $G = (V, E)$ into a new graph $G'$ as follows: The vertices of $G'$ should be $V \times \{0,1\}$. For every vertex $v \in V$, include the edge from $(v, 0)$ to $(v, 1)$ with weight zero. For every edge $(u,v) \in E$ with weight $l$, include the edge from $(u,0)$ to $(v,0)$, the edge from $(u,1)$ to $(v,1)$, and the ...


1

There was a paper on the arxive last month, dealing with this generalization of the TSP: The multi-stripe travelling salesman problem Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger (Submitted on 20 Sep 2016) https://arxiv.org/abs/1609.09796 The problem does not seem to have a particular name in the literature.


Only top voted, non community-wiki answers of a minimum length are eligible