Parameterized Complexity of Finding Dissimilar Shortest Paths

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 ∈ V, and integers $d, k$, the goal of Dissimilar Shortest Paths is to decide whether D has k shortest paths P₁, , Pₖ from s to t such that |A(Pᵢ) A(Pⱼ)| ≥ d for distinct Pᵢ and Pⱼ. We design a deterministic algorithm to solve Dissimilar Shortest Paths with running time 2O(3ᵏdk²)nO(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.