# Finding a cycle of a specific length in an edge-weighted graph

I'm looking for some suggestions on how we might calculate cycles of a specific length in an edge-weighted graph.

For example, imagine my phone tells me that I need to walk three miles today. It might be nice if the phone could calculate a few tours of appropriate length, ideally avoiding things like walking up and down the same streets repeatedly.

A previous posting reviewed some algorithms for finding fixed-length cycles in unweighted graphs. However, I'm not aware of anything concerning the edge-weighted case.

A simple algorithm for a road network might work as follows. Assume that I want a cycle of length $$x$$ that starts and ends at a source vertex $$s$$. Now use Dijkstra's algorithm to produce a shortest path tree. Next, find the node $$v$$ in this tree whose distance from $$s$$ is close to $$x/2$$. Our solution then involves walking from $$s$$ to $$v$$ and then back to $$s$$ again. While this algorithm is polynomial, the solution is not great as we will end up walking up and down the same streets (so its not really a cycle at all...).

Another option might be to convert a weighted graph into an unweighted one. Assuming all edge-weights are integer, an edge of length $$x$$ is replaced by a chain of $$x-1$$ vertices, as the following demonstrates:

How to convert an edge weighted graph into an unweighted graph

We can then apply methods used for the unweighted graphs. An issue with this approach is that it could massively increase the size of the graph. Given that existing approaches for simple graphs can be quite expensive, this doesn't seem like a good idea.

Does anyone have any ideas/thoughts?

• if your cycles must not re-visit vertices, then it's a hard problem, as hard as TSP. Jan 9 '20 at 14:15
• @DimaPasechnik If you just do not want to revisit edges, there is a trivial realization of the knapsack problem in the given setup: just consider the graph with 2 vertices and multiple edges of lengths $0,w_1,\dots,w_n$ between them. Then just ask if you can make a path of length exactly $W$. However, as the setup suggests, we do not really need to achieve exactly $W$: a multiplicative factor close to $1$ should be allowed, in which case knapsack is just polynomial, so there is some hope. Of course, the minimal length computation is a red herring if we want just to stroll, not to get anywhere. Jan 9 '20 at 17:58