Is there an efficient algorithm to find GCD of all cycles' lengths in directed multigraph?

Question

I have weighted connected directed graph with cycles which can have multiple edges and loops (edge from vertex back to itself). Weight of each edge is its length (always positive integer). There always is a path from vertex $v_0$ to every other vertex (including itself).

I need to find greatest common divisor (GCD) of all cycles' (from $v_0$ to itself) lengths. It always exists and is a divisor of shortest cycle (from $v_0$ to itself) length. Note that concatenating any number of such cycles also gives valid cycle.

I know one way to find GCD. We can find generating function of number of cycles of certain length (using Gaussian elimination for example). Such generating function is always a rational function (ratio of polynomials). Then GCD of $x$ powers from denominator is actually GCD of all cycle lengths. However this is really computationally inefficient. Finding generating function always requires near cubic rational function arithmetic operations (cubic for Gaussian elimination but can be less if use sophisticated matrix multiplication, but that is not practical). However those arithmetic operations are exponential in time because coefficients grow exponentially (at least). There is possibility to simplify graph a bit by contracting vertices without loops and merge multiple loops on vertices, but that does not help much.

I am wondering if there is more efficient algorithm to solve this problem. Maybe there are papers on similar subject, however I did not find any.

Here you can see example of such graph. It has GCD=10.

Answer 1

I think this actually has really simple solution. I haven't checked it programmatically yet, but it seems right to me. Please comment if you think it does not work.

Main difficulty were loops. But we can efficiently get rid of them. "Eureka" moment was when I realized that position of loops doesn't matter, we can move them anywhere (i.e. to $v_0$ itself).

Suppose there is path from $v_0$ to $v_0$ passing through $v_1$ which has loop with length $l$, length of path's part before $v_1$ is equal to $L_0$ and after $v_1$ accordingly $L_1$. Then length of such path is $L_0+L_1$. Consider another path which follows exactly same vertices but includes also that loop of $v_1$. Then length of this path is $L_0+L_1+l$. Then GCD of all paths from $v_0$ to $v_0$ is equal to

$$GCD(L_0+L_1,L_0+L_1+l,\ldots)=GCD(L_0+L_1,L_0+L_1+l-(L_0+L_1),\ldots)=GCD(L_0+L_1,l,\ldots)$$

by property of GCD. So that is the same result as if loop of length $l$ would be separate path of length $l$, and we can achieve that by moving loop to $v_0$.

A bit expanding this argument, we can move all loops from all vertices to $v_0$. By grouping GCD arguments, we can see that we then can replace all loops by one of length which is equal to GCD of lengths of all loops, name it $g$.

Then we recursively contract all other vertices (removing vertex by combining all incoming and outcoming edges), now without loops it is easily done. Usually doing so increases number of edges exponentially. However we can use again property of GCD and reduce edge lengths modulo $g$. This way we keep number of edges bounded. After no vertices are left except $v_0$, we compute GCD of all loops on $v_0$ and that is our final answer. If new loop is created during contracting a vertex, then we update $g$ as $g'=GCD(g,l)$, where $l$ is length of new loop, and remove that loop.

We can make other optimizations as well. For example we can remove multiple edges. Suppose we have vertices $v_1$ and $v_2$ with 3 edges from $v_1$ to $v_2$ with lengths $a$, $b$ and $c$, $L_1$ being length of path from $v_0$ to $v_1$, $L_2$ being length of path from $v_1$ to $v_0$, then GCD of all , then GCD of all paths from $v_0$ to $v_0$ is equal to

$$GCD(L_0+a+L_1,L_0+b+L_1,L_0+c+L_1,\ldots)=GCD(L_0+a+L_1,b-a,c-a,\ldots)$$

by same property of GCD. So we can choose any one edge to leave and remove other, updating $g$ as $g'=GCD(g,b-a,c-a)$. Here potentially we can cleverly choose which edge is more beneficial to leave.

Also there is possibility to stop algorithm early, if $g$ becomes $1$ (or GDC of all edge lengths).

Here is illustration of the procedure for example graph from question: