# Tag Info

26

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

17

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

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

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

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

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

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

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

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

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

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

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

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

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