Parameterized Complexity of Finding Dissimilar Shortest Paths
<|reference_start|>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 \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$.<|reference_end|>
@article{funayama2024parameterized,
    title={Parameterized Complexity of Finding Dissimilar Shortest Paths},
    author={Ryo Funayama, Yasuaki Kobayashi, Takeaki Uno},
    journal={arXiv preprint arXiv:2402.14376},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.14376},
    primaryClass={cs.DS}
}