4
$\begingroup$

Let $G = (V, E)$ be an undirected graph without self loops and with edge weights $w: E \to \mathbb{N}$. The girth $g(G)$ of $G$ is defined as the length of the shortest cycle in $G$, i.e.

$g(G) := \min\left\{ n \in \mathbb{N} \mid \exists \text{ cycle }(e_1, e_2, \dots, e_k) \text{ in $G$ satisfying } n = \sum_{i = 1}^k w(e_i) \right\}$.

GOAL. Determine $g(G)$ algorithmically and as efficient as possible in terms of time complexity. Note that it's not necessary to find corresponding cycle, length is sufficient.

I present my thoughts on this problem as following. If the graph is unweight, i.e. $w(v) = 1$ for all $v \in V$, we may start a breadth-first search traversal keeping track of the depth of each vertex. Once we detect an edge which leads to an already visited vertex $v$, a cycle is found. The length of the cycle is the difference of the current depth and the depth of $v$. BFS from each vertex and taking minimum should do the job, time complexity is $\mathcal{O}(|V| \times (|V| + |E|))$.

How to deal with edge weights? It seems natural to modify Dijkstra, but I do not see how, because the cycle with least edges may be different from the cycle of minimum weight, the shortest cycle. Is there still a way to use Dijkstra in order to solve this problem?

Can we adapt an all-pairs shortest path algorithm? I would appreciate a solution based on Floyd-Warshall, because of it's simplicity (if there is no faster algorithm). One may assume the graph to be dense, i.e. $|E| = \mathcal{O}(|V|^2)$, so the above solution is $\mathcal{O}(|V|^3)$.

$\endgroup$
2
$\begingroup$

You can use both algorithms to solve this problem (Dijkstra's and Floyd-Warshall's) and you do not need to adapt them: you can simply use their output.

As suggested in D.W.'s answer, you can compute the minumum $d(v,v)$ over all $v \in V$. Each value $d(v,v)$ represents the length of the shortest way to get from a vertex $v$ back to the same vertex $v$; that is, the shortest cycle through $v$. Therefore, the minimum $d(v,v)$ over all vertices represents the shortest cycle in the entire graph $G$.

To gain more intuition, note that the shortest cycle in $G$ will go through some vertices $\{v_1, v_2, ..., v_k\}$, and that $d(v_1,v_1) = d(v_2,v_2) = \: ... \: = d(v_k,v_k)$. You need to find the minimum $d(u, v)$ (where $u = v$) in the whole graph $G$. This information can be easily obtained by inspecting the diagonal of the output matrix of an all-pairs shortest-paths algorithm.

Observe that the above reasoning would not be valid if $G$ had negative edge weights, and you were looking for a simple cycle. This is because nothing prevents the algorithm from selecting the same edge twice.

Observe also that if the graph is a tree (i.e., it contains no cycles), then the girth can be considered to be infinity. This can be checked in a simple pre-processing step, using, for example, breadth-first search.

With respect to the running time, $|V|$ invocations to Dijkstra's algorithm will probably be faster - $O(|V|^2 \log |V|)$ - if the graph is sparse. If the graph is dense, Floyd-Warshall's algorithm is probably a better choice.

$\endgroup$
3
$\begingroup$

Use an all-pairs shortest-paths algorithm to find the distance from each vertex to each other vertex, call it $d(u,v)$. Now find the minimum value of $d(v,v)$ over all vertices $v$. That is the length of the shortest cycle.

Why does this work? Suppose the shortest cycle from $v$ to $v$ has length $\ell$. Obviously we will have $d(v,v) \le \ell$ (since we have a path from $v$ to $v$ of length $\ell$, the shortest such path is at most $\ell$). Conversely, we know there is a path of length $d(v,v)$ from $v$ to $v$; since it goes from $v$ to $v$, this is a cycle; so the length $\ell$ of the shortest cycle must satisfy $\ell \le d(v,v)$. We have proven both $d(v,v) \le \ell$ and $\ell \le d(v,v)$, so it follows that $\ell = d(v,v)$.

$\endgroup$
  • $\begingroup$ Why does this work? It sounds plausible but I don't see how to prove it. $\endgroup$ – neutron-byte Sep 16 '17 at 22:20
  • $\begingroup$ @neutron-byte, see revised answer for a proof. $\endgroup$ – D.W. Sep 17 '17 at 3:53
  • $\begingroup$ There is a problem. Consider the graph consisting of only two vertices connected with a single undirected (as stated in question) edge with weight 1. Obviously, the graph contains no cycle. But Floyd-Warshall yields $d[v][v] = 2$ for this vertex... I think your algorithm does only work in directed graphs. $\endgroup$ – neutron-byte Sep 17 '17 at 15:12
  • $\begingroup$ @neutron-byte, that actually is a cycle -- it's just not a simple cycle. $\endgroup$ – D.W. Sep 18 '17 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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