# Parameterized Complexity of Finding Dissimilar Shortest Paths

Preprint · Ryo Funayama, Yasuaki Kobayashi, Takeaki Uno

- Archive id: arxiv:2402.14376
- Published: 2024-02-22
- arXiv: https://arxiv.org/abs/2402.14376
- Citations: 0
- Source URL: https://arxiv.org/abs/2402.14376
- PDF: https://arxiv.org/pdf/2402.14376
- Provenance: arxiv

## Abstract

We consider the problem of finding \`\`dissimilar'' $k$ shortest paths from $s$ to $t$ in an edge-weighted directed graph $D$, where the dissimilarity is measured by the minimum pairwise Hamming distances between these paths. More formally, given an edge-weighted directed graph $D = (V, A)$, two specified vertices $s, t \\in V$, and integers $d, k$, the goal of Dissimilar Shortest Paths is to decide whether $D$ has $k$ shortest paths $P\_1, \\dots, P\_k$ from $s$ to $t$ such that $\|A(P\_i) \\mathbin{\\triangle} A(P\_j)\| \\ge d$ for distinct $P\_i$ and $P\_j$. We design a deterministic algorithm to solve Dissimilar Shortest Paths with running time $2^{O(3^kdk^2)}n^{O(1)}$, that is, Dissimilar Shortest Paths is fixed-parameter tractable parameterized by $k + d$. To complement this positive result, we show that Dissimilar Shortest Paths is W\[1\]-hard when parameterized by only $k$ and paraNP-hard parameterized by $d$.

_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.