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