# Tag Info

78

So, I skimmed through the papers, and this is what I gleamed. If there is anyone more knowledgable in the subject-matter, please correct me if I'm wrong (or add your own answer, and I will accept it instead!). Links to each paper can be found in the question-post, above. Simple recalculations D* (aka Dynamic A*) (1994): On the initial run, D* runs very ...

23

Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles. This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the ...

16

A major open problem in mathematical programming is designing a strongly polynomial time linear programming algorithm. A related problem is whether any variant of the simplex algorithm runs in strongly polynomial time. It makes sense to first prove strong polynomial time bounds for variants of simplex applied to problems for which we already know strong ...

16

There's a big caveat when using D*, D*-Lite, or any of the incremental algorithms in this category (and it's worth noting that this caveat is seldom mentioned in the literature). These types of algorithms use a reversed search. That is, they compute costs outwards from the goal node, like a ripple spreading outwards. When the costs of edges change (e.g. you ...

12

Probably the simplest approach is to perturb the edge weights symbolically rather than numerically. Intuitively, you'd like to reassign the weight of each edge as $$\tilde{w}(e) = w(e) + \varepsilon \cdot w'(e)$$ where $w(e)$ is the original edge weight, $w'(e)$ is a secondary edge weight, and $\varepsilon$ is a global scaling factor. This perturbation ...

11

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 $... 10 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 The main idea is to use an incremental algorithm, that is able to take advantage of the previous calculations when the initial calculated route gets blocked. This is often investigated in the context of robots, navigation and planning. Koenig & Likkachev, Fast replanning for Navigation in Unknown Terrain, IEEE Transactions on Robotics, Vol. 21, No. 3, ... 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-... 9 The eccentricity of a vertex$v$is the length of a longest shortest path starting from$v$. The diameter is the maximal eccentricity over all vertices. Any BFS from a vertex will establish its eccentricity. A key idea for efficient diameter finding is therefore to preprocess the graph to find a small set of vertices, at least one of which achieves maximal ... 8 It is an open problem to lower bound the difference between two distinct Euclidean TSP tours by an inverse polynomial in the input size. Such a lower bound would show that Euclidean TSP is an NP optimizaition problem, which is not known. Let us assume that a Euclidean TSP instance is given by a collection of points in$(\mathbb{Z} \cap [-N, N])^2$(i.e. ... 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 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. 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 ...

6

Just an extended comment to include the picture: if the following (random) resistor network is valid then the max current flow 33.9mA is not on the shortest path from $s$ (+5V) to $t$ (GND).

5

You can treat this as a directed graph problem, where the weights of all edges coming into a node are equal to that node's weight. If the edges are weighted too, add the node's weight and the edge's weight together to find the incoming edge's weight in the directed graph.

5

The main reason is that the non-constant degree would imply that the time per result is too high. The number of nodes found by the search, in the end, is going to be k, but all but the last one needs to have their children expanded, so the number of expanded nodes is kd where d is the degree. Unless d is O(1) this will be larger than the eventual time bound ...

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

I'd like add something about rapidly-exploring randomized trees, or RRTs. The basic idea has good discussion all over the internet, but it's probably safe to start with the links off the Wikipedia page and with Kuffner and LaValle's original papers on the topic. The most important feature of RRTs is that they can deal with real-valued spaces of extremely ...

4

There have been many results on distance oracles and approximate distance oracles for directed graphs. A distance oracle for a graph is a data structure which can be queried on any pair of vertices (u,v) and returns the distance from u to v. It might also return the path realizing this distance. A good place to start (for the undirected case) would be: ...

4

First, let's be completely clear about the definition of the multiple-source shortest path problem. The input consists of the following: a directed planar graph $G = (V,E)$ with $n$ vertices; a non-negative weight $w(e)$ for every directed edge $e$; an embedding of $G$ into the plane; and a distinguished face $f$ of this planar embedding (the "outer" face)....

4

theory results: exact: Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006) approximate: Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218 ...

4

Your solution might consist of a path plus several edge-disjoint cycles.

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

The mentioned block graphs in the question are distance-hereditary. A linear time algorithm for computing the diameter for distance-hereditary graphs is given in  (see Theorem 5).  Dragan, Feodor F. Dominating cliques in distance-hereditary graphs. Springer Berlin Heidelberg, 1994.

3

Something has gone wrong, here. Let us start with the basic definitions. A Hamiltonian cycle is a cycle is an enumeration $v_1, \dots, v_n$ of the vertices of a graph such that there is an edge from $v_i$ to $v_{i+1}$ for $1\leq i<n$ and an edge from $v_n$ to $v_1$. In the Traveling Salesman Problem (TSP), we are given $n$ cities and, for every pair of ...

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