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.1k
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.1k
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
  • 12k

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