Skip to main content
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 ...
David Eppstein's user avatar
8 votes
Accepted

Shortest distance problem with length as functions of time

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 ...
Hsien-Chih Chang 張顯之's user avatar
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 ...
Denis's user avatar
  • 8,903
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 ...
GMB's user avatar
  • 2,403
5 votes
Accepted

Are there any heuristics that works solely on graphs?

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 ...
Michael N. Rice's user avatar
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 ...
Gamow's user avatar
  • 5,772
4 votes

Constant Width Max Sum Product Multi-objective Shortest path problem

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 ...
Denis's user avatar
  • 8,903
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 ...
tmn's user avatar
  • 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 ...
Neal Young's user avatar
  • 10.8k
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 ...
Laakeri's user avatar
  • 1,786
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 ...
NaturalLogZ's user avatar
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 ...
Neal Young's user avatar
  • 10.8k
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 ...
Mikhail Rudoy's user avatar
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 ...
GMB's user avatar
  • 2,403
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 ...
D.W.'s user avatar
  • 12.2k
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)$. ...
Clement C.'s user avatar
  • 4,471
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$...
Neal Young's user avatar
  • 10.8k
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/...
JimN's user avatar
  • 1,318
3 votes

Shortest distance problem with length as functions of time

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 ...
Ryan Williams's user avatar
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 ...
Neal Young's user avatar
  • 10.8k
2 votes
Accepted

Max Sum Product Multi-objective Shortest path problem

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 ...
Denis's user avatar
  • 8,903
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-...
Neal Young's user avatar
  • 10.8k
2 votes

What is the proof that visibility graphs can be used to compute the shortest path?

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 ...
saul.shanabrook's user avatar
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: ...
Neal Young's user avatar
  • 10.8k
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 ...
D.W.'s user avatar
  • 12.2k
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. ...
Changxin Cao's user avatar
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 ...
Shaull's user avatar
  • 5,656
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 ...
Sandeep Silwal's user avatar
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 ...
Rajat De's user avatar
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 ...
Florian K's user avatar

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