3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ if your cycles must not re-visit vertices, then it's a hard problem, as hard as TSP. $\endgroup$
    – Dima Pasechnik
    Commented Jan 9, 2020 at 14:15
  • $\begingroup$ @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. $\endgroup$
    – fedja
    Commented Jan 9, 2020 at 17:58

2 Answers 2

Reset to default
1
$\begingroup$

To help answer my own question, here's a paper that I recently published on this topic. Thanks also for the suggestions of Manfred Weis above.

Lewis, R. and P. Corcoran (2022) 'Finding Fixed-Length Circuits and Cycles in Undirected Edge-Weighted Graphs: An Application with Street Networks'. Journal of Heuristics, vol. 28, pp. 259-285.

https://link.springer.com/content/pdf/10.1007/s10732-022-09493-5.pdf

Improve this answer
$\endgroup$
0
$\begingroup$

There are the so-called diverse routing algorithms that manage to calclulate the edge-disjoint or vertex-disjoint pair of paths with minimal lengths-sum between a pair of vertices. With such an algorithm you can check all pairs of points and filter out the ones, that have path-sum that comes close enough to the desired cycle length.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .