Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
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

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.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 ...
D.W.'s user avatar
  • 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. ...
Changxin Cao's user avatar

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