12
votes
Accepted
Number of simple paths between two vertices in a DAG
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 ...
- 51.2k
5
votes
Accepted
Shortest path property and monadic second order logic
I'm assuming you want a formula $\varphi(s,t,X)$ in $MSO_2$ on graphs, stating that the set $X$ is the shortest path from $s$ to $t$. Under this meaning of "express the shortest path", no ...
- 9,018
5
votes
Accepted
Axioms for Shortest Paths
I just stumbled across this old question while conducting a lit search, and I happen to have recently gotten answers in this paper that I might as well share. I hope the combination of thread ...
- 2,531
4
votes
How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?
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 ...
- 5,792
4
votes
Finding k shortest Paths with Eppstein's Algorithm
Pseudocode for Eppstein's algorithm (and the authors' lazy version of it) are given in:
V.M. Jiménez, A. Marzal, A lazy version of Eppstein’s shortest paths algorithm, in: 2nd International Workshop ...
- 41
4
votes
Accepted
Shortest path on a hypergraph with no leftovers
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 ...
- 10.9k
4
votes
Accepted
Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges
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 ...
- 1,901
4
votes
Accepted
Polynomial time algorihtms for two variants of the decision version of longest walk problem
I deleted my previous answer because there were some inaccuracies. Also I am going to assume that either, you are looking for the longest walk, with any nodes as endpoints, or you are looking for a ...
- 442
3
votes
Accepted
Shortest path with permutations and fixed dimension
Summary:
A dimension restriction is necessary. Lemma 2 below observes that if arbitrary dimension is allowed the problem (even restricted to permutation matrices) is at least as hard as Graph ...
- 10.9k
3
votes
Accepted
Shortest path with affine updates and fixed dimension
Lemma 1. The problem is strongly NP-hard for $n=2$, even in directed acyclic graphs (DAGs).
[EDIT: strong NP-hardness depends on the encoding. See the comments at the end.]
Proof sketch. The proof is ...
- 10.9k
3
votes
Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time
The discussion in this paper, Section 3 beginning on page 7, might be useful to you. It focuses on reducing distance product witnesses to distance product, which is the same as distance vs path APSP ...
- 2,531
3
votes
Accepted
Finding shortest path while maximizing the number of overlapping edges
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 ...
- 12.4k
3
votes
Accepted
What exactly is Lawler's modification to Yen's algorithm and how does it work?
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)$.
...
- 4,491
3
votes
Accepted
Minimum Union-Sum Cost Path
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$...
- 10.9k
3
votes
Bellman-Ford with Non-edge-decomposable Path Weights
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 ...
- 2,913
3
votes
Accepted
How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?
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/...
- 1,318
2
votes
Dynamic programming and shortest path problem
Here's a less formal answer that I hope nonetheless addresses the spirit of the question.
Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-...
- 10.9k
2
votes
Accepted
Proof of SPFA's worst-case complexity?
Here's the algorithm (from the wikipedia page) then a proof of the time bound:
...
- 10.9k
2
votes
Shortest path with permutations and fixed dimension
The usual rule is to ask only one question per post. I'll answer the first, about $A=\text{Id}$. For that special case, the shortest path problem is easy to solve in polynomial time. I'll describe ...
- 12.4k
1
vote
Accepted
Shorter than target vector path algorithm
The problem is NP-hard, even in just two dimension, by reduction from the knapsack problem.
Consider a 0-1 knapsack instance with $n$ items, where the weight of the $i$th item is $w_i$ and its value ...
- 12.4k
1
vote
Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs
This problem appears to be an NP problem, and here's a proof for it. Considering the presence of fixed setup costs in the problem, it brings to mind the uncapacitated facility location problem. ...
- 21
1
vote
Accepted
Multi agent path following with collision avoidance with pre-determined path
In general, your problem is NP-hard, naturally (if you have arbitrarily many agents and an arbitrary arena, of course).
Combining paths will naturally cause collisions (otherwise we wouldn't need ...
- 5,636
1
vote
When is extra vertex required in arbitrage detection using Bellman Ford?
Yes there is no reason to add the extra vertex $v_0$ since the graph is fully connected and every vertex is reachable from every other vertex (the table specified in the problem seems to be a complete ...
- 152
1
vote
Finding Cheapest n-Path
I am assuming you are given a weighted directed acyclic graph with source $s$ and destination $t$ and you want to find the shortest path from $s$ to $t$ with length exactly $n$ , this can be done ...
- 94
1
vote
Accepted
Maximum difference between two shortest paths
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 ...
- 31
1
vote
Multiple source shortest path with one reversal
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 ...
- 2,913
1
vote
K-fold Traveling salesman problem - A variant of TSP
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
(...
- 5,792
1
vote
Anyone recognize this as a special type of multi-commodity flow problem?
I think you can solve this as a single shortest path problem with respect to arc weights
$$\overline{w}_{ij}=\min\{-w_{ijp}\ :\ p\in\{1,\ldots,m\}\}.$$
For every arc $(i,j)$ fix some $p(i,j)\in\{1,\...
- 1,036
1
vote
Shortest distance problem with length as functions of time
If you assume that the times are integral (which makes sense in the case of public transit), you can make a time-expanded network, similar to the one suggested by Ford-Fulkerson for max-flow over time ...
- 463
Only top scored, non community-wiki answers of a minimum length are eligible