# Finding $k$ Simple Shortest Paths and Cycles

Article · Udit Agarwal, Vijaya Ramachandran

- Archive id: arxiv:1512.02157
- Published: 2015-12-07
- DOI: https://doi.org/10.4230/lipics.isaac.2016.8
- arXiv: https://arxiv.org/abs/1512.02157
- Citations: 6
- Source URL: https://arxiv.org/abs/1512.02157
- PDF: https://arxiv.org/pdf/1512.02157
- Provenance: arxiv

## Abstract

The problem of finding multiple simple shortest paths in a weighted directed graph $G=(V,E)$ has many applications, and is considerably more difficult than the corresponding problem when cycles are allowed in the paths. Even for a single source-sink pair, it is known that two simple shortest paths cannot be found in time polynomially smaller than $n^3$ (where $n=\|V\|$) unless the All-Pairs Shortest Paths problem can be solved in a similar time bound. The latter is a well-known open problem in algorithm design. We consider the all-pairs version of the problem, and we give a new algorithm to find $k$ simple shortest paths for all pairs of vertices. For $k=2$, our algorithm runs in $O(mn + n^2 \\log n)$ time (where $m=\|E\|$), which is almost the same bound as for the single pair case, and for $k=3$ we improve earlier bounds. Our approach is based on forming suitable path extensions to find simple shortest paths; this method is different from the \`detour finding' technique used in most of the prior work on simple shortest paths, replacement paths, and distance sensitivity oracles. Enumerating simple cycles is a well-studied classical problem. We present new algorithms for generating simple cycles and simple paths in $G$ in non-decreasing order of their weights; the algorithm for generating simple paths is much faster, and uses another variant of path extensions. We also give hardness results for sparse graphs, relative to the complexity of computing a minimum weight cycle in a graph, for several variants of problems related to finding $k$ simple paths and cycles.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.