Share Your Experience: Take the 2024 Developer Survey

# Tag Info

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 ...
• 429
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.8k
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.8k

### 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.1k
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.1k
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. ...

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