Finding k Simple Shortest Paths and Cycles
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Presents a new algorithmic framework using path extensions plus distance‑sensitivity tools to compute K simple shortest paths and cycles. Claims an all‑pairs solution for K=2 in Õ(MN) time (matching lower bounds via MN reductions from Minimum Weight Cycle), a faster O(MN^2) algorithm for K=3, and an enumeration routine that spends O(M) for the first path and about O(log n) per additional path for constant K. Reductions and experiments show the approach works and the Õ(MN) bound is likely tight for sparse graphs.
AI-written summary · about
chapters (21)
- 0:00Introduction to paths
- 0:15K-shortest paths variants
- 1:31Simple paths problem
- 2:50Clarifying path constraints
- 5:55Complexity and prior work
- 9:10Problems studied
- 10:19Main contributions
- 12:30Systematic study and bounds
- 13:46Sparse graph hardness
- 16:02Detailed algorithmic results
- 19:13Reductions explained
- 22:28Transformation proof
- 27:32Summary of complexity
- 29:04Limitations of detour methods
- 31:45All-pairs replacement paths
- 34:12Two-phase approach
- 37:10Generalizing Qk sets
- 39:24Path extension lemma
- 42:03Priority queue algorithm
- 45:19Future work and conclusion
- 48:08Questions and answers