3
$\begingroup$

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.

Graph example

$\endgroup$
2
  • $\begingroup$ Do you know about a blog post or paper that describes how you can obtain such a generating function from a graph with more detail? $\endgroup$
    – plshelp
    Commented Apr 15, 2022 at 17:31
  • $\begingroup$ @plshelp There is some explanation in "Analytic Combinatorics" by Philippe Flajolet and Robert Sedgewick, pages 356-357. $\endgroup$
    – Somnium
    Commented Apr 15, 2022 at 20:29

1 Answer 1

2
$\begingroup$

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:

algorithm illustration

$\endgroup$
3
  • 1
    $\begingroup$ Nice illustrations. Contracting one vertex may generate $O(n^2)$ new edges. Contracting $n-1$ vertices means $O(n^3)$ time-complexity. Is that right? Is that fast enough? I was seeking an $o(n^3)$ algorithm. $\endgroup$
    – John L.
    Commented Apr 15, 2022 at 23:51
  • $\begingroup$ What do you mean by a "loop"? Do you mean an edge from a particular vertex back to itself? Do you mean a cycle starting from a particular vertex? $\endgroup$
    – D.W.
    Commented Apr 17, 2022 at 3:10
  • $\begingroup$ @D.W. Edge back to itself. I believed it is standard name for it, maybe I am wrong. I updated question. $\endgroup$
    – Somnium
    Commented Apr 17, 2022 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.