Algorithm for finding shortest "k stride" path in graph

1
votes

The graph is unweighted and undirected.

Given two vertices s and t, and stride k, I want to find the shortest path between them that is:

  1. Of length divisible by k

  2. Every k "steps" in the path, counting from the first, are a simple path.

Meaning, the shortest non-simple path that can only "jump" k vertices at every step (exactly k), and every "jump" must be a simple sub-path.

I think this problem is equal to constructing a second graph, G', where (u, v) are an edge in G' if there exists a path of length k in G, because a BFS scan would give the required path -- but I haven't been able to construct such a graph in reasonable time (apparently it's an NP problem). Is there an alternative algorithm?

1
algorithmgraphgraph-algorithm

1 Answers

2
votes

The problem you're describing is NP-hard overall because you can reduce the Hamiltonian path problem to it. Specifically, given an n-node graph and a pair of nodes s and t, you can determine whether there's a Hamiltonian path from s to t by checking if the shortest (n-1)-stride path from s to t has length exactly n-1, since in that case there's a simple path from s to t passing through every node once and exactly once. As a result, if k is allowed to be large relative to n, you shouldn't expect there to be a particularly efficient algorithm for solving this problem.

In case it helps, there are some fast algorithms for finding long simple paths in graphs that might work really well for reasonable values of k. Look up the color-coding technique, in particular, as an example of this.