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 2^O (3ᵏdk²) 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 W1-hard when parameterized by only k and paraNP-hard parameterized by d.