A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
Heman Shakeri, Torben Amtoft, Behnaz Moradi-Jamei, Nathan Albin, Pietro Poggi-Corradini · 2025
Read A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies by Heman Shakeri, Torben Amtoft, Behnaz Moradi-Jamei, Nathan Albin, Pietro Poggi-Corradini (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-01049.txt.
Introduction
Heman Shakeri and four coauthors give a fast algorithm for finding light cycles in graphs in a 2025 paper. Cycles are basic features of networks, shaping robustness, information flow, community structure, and dynamics. Tools that probe cyclic structure are in demand across graph mining, network optimization, bioinformatics, and social network analysis.
Their algorithm finds minimum weight cycles, the cheapest loops under edge costs, in cyclic graph topologies used in mining. Faster cycle finding helps analysts spot feedback loops and redundant paths in huge networks. The paper aims for efficiency without losing exactness about which cycle is lightest.
Catalog record
| CREATOR | Heman Shakeri, Torben Amtoft, Behnaz Moradi-Jamei, Nathan Albin, Pietro Poggi-Corradini |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-01049
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies Heman Shakeri, Torben Amtoft, Behnaz Moradi-Jamei, Nathan Albin, Pietro Poggi-Corradini Abstract Cyclic structures are fundamental topological features in graphs, playing critical roles in network robustness, information flow, community structure, and various dynamic processes. Algorithmic tools that can efficiently probe and analyze these cyclic topologies are increasingly vital for tasks in graph mining, network optimization, bioinformatics, and social network analysis. A core primitive for quantitative analysis of cycles is finding the Minimum Weight Cycle (MWC), representing the shortest cyclic path in a weighted graph. However, computing the MWC efficiently remains a challenge, particularly compared to shortest path computations. This paper introduces a novel deterministic algorithm for finding the MWC in general weighted graphs ( github.com/Shakeri-Lab/girth ). Our approach adapts the structure of Dijkstra’s algorithm by introducing and minimizing a composite distance metric, effectively translating the global cycle search into an iterative node-centric optimization. We provide a rigorous proof of correctness based on loop invariants. We detail two mechanisms for accelerating the search: a provable node discarding technique based on intermediate results, and a highly effective graph pruning heuristic. This heuristic dynamically restricts the search to relevant subgraphs, leveraging the principle of locality often present in complex networks to achieve significant empirical speedups, while periodic resets ensure global optimality is maintained. The efficiency of the proposed MWC algorithm enables its use as a core component in more complex analyses focused on cyclic properties. We illustrate this through a detailed application case study: accelerating the computation of the Loop Modulus, a measure of cycle richness used in advanced network characterization ( github.com/Shakeri-Lab/loop_modulus ). Our algorithm dramatically reduces the runtime of the iterative constraint-finding bottleneck in this computation. 1 School of Data Science, University of Virginia 2 Department of Mathematics and Statistics, University of Kansas 3 Department of Computer Science, Kansas State University 4 Department of Mathematics, Kansas State University * Corresponding author: [email protected] 1 Problem Statement and Framework Cyclic structures permeate real-world networks and abstract graph representations, influencing phenomena ranging from network resilience and transport efficiency to the formation of communities and the behavior of dynamic systems [ 3 ] . Effectively analyzing these cyclic topologies requires robust algorithmic primitives. A cornerstone primitive is the computation of the Minimum Weight Cycle (MWC), often referred to as the (weighted) girth of the graph [ 7 ] . Finding the MWC is fundamental not only in graph theory itself but also serves as a building block for applications such as computing minimal cycle bases [ 6 , 9 , 10 ] , analyzing cycle packing problems [ 2 , 11 , 20 ] , understanding graph connectivity and chromatic properties [ 3 , 4 ] , and even solving related problems like min-cut in planar graph duals [ 21 ] . Furthermore, efficient MWC computation is crucial for network analysis techniques like Loop Modulus, which quantifies the richness of cycle families [ 22 ] . Despite its importance, finding the MWC in general weighted undirected graphs algorithmically is considerably more challenging than finding shortest paths between vertex pairs. Let G=(V,E,w) be an undirected graph with vertex set V , edge set E , and a positive edge weight function w:E\to\mathbb{R}_{>0} . A path \pi is a sequence of distinct vertices v_{0},v_{1},\dots,v_{r} such that (v_{i-1},v_{i})\in E for all i=1,\dots,r . A simple cycle c is a sequence of vertices v_{0},v_{1},\dots,v_{r} where v_{0}=v_{r} , r\geq 3 , and v_{1},\dots,v_{r} are distinct. We denote the set of vertices in a path or cycle \pi as \text{vertices}(\pi) . The length of a path \pi=(v_{0},\dots,v_{r}) or cycle c=(v_{0},\dots,v_{r}) is the sum of its edge weights: \ell(\pi):=\sum_{i=1}^{r}w(v_{i-1},v_{i}). (1) The shortest path distance d(x,y) between vertices x,y\in V is the minimum length \ell(\pi) over all paths \pi from x to y . If no path exists, d(x,y)=\infty . The Minimum Weight Cycle (MWC) problem seeks to find a simple cycle c^{*} in G such that \ell(c^{*})=\min_{c\in\mathscr{C}}\ell(c) , where \mathscr{C} is the set of all simple cycles in G . We assume G is not a tree (or a forest), so \mathscr{C} is non-empty. Existing Approaches and Challenges Significant effort has been invested in developing algorithms for the MWC problem. For unweighted graphs, Itai and Rodeh [ 8 ] presented algorithms with subcubic time complexity related to matrix multiplication, though the weighted case was left open. Subsequent work extended these ideas to integer weights [ 19 ] and established connections between MWC and other challenging graph problems [ 25 ] . Approximation algorithms [ 8 , 18 , 12 , 27 , 17 ] , randomized algorithms [ 27 ] , and specialized algorithms for finding even-length cycles [ 26 ] have also been developed. A common strategy employed by many deterministic MWC algorithms for weighted graphs involves searching for the shortest cycle passing through a specific vertex or edge. The standard baseline, often called the Rooted Girth Algorithm , iterates through every edge e=(u,v)\in E . For each edge, it computes the shortest path distance d_{G\setminus e}(u,v) in the graph without edge e . The minimum of d_{G\setminus e}(u,v)+w(e) over all edges is the MWC. This requires |E| shortest path computations. Alternatively, one can adapt all-pairs shortest path algorithms or run multiple shortest path searches (like Dijkstra’s) from each vertex v , looking for the shortest path between neighbors u,z of v in the graph G\setminus\{v\} . Using efficient implementations (e.g., Fibonacci heaps), this leads to overall complexities like O(|V||E|+|V|^{2}\log|V|) or related bounds [ 8 , 27 , 16 ] . While effective, these approaches repeatedly explore large portions of the graph. x y_{1} y_{2} w_{1} w_{2} w_{3} w_{4} c_{1} c_{2} Edge with weight Distance path d(x,c) Cycle with length \ell(c) Figure 1: Composite distance d^{+}(x,c) is the shortest path distance from vertex x to cycle c plus c ’s length \ell(c) . The plot shows cycles c_{1} and c_{2} with edge weights. The Minimum Weight Cycle (MWC) length is \ell(c^{*})=\min_{x\in V}\min_{c\in\mathscr{C}}d^{+}(x,c) . 1.1 An Alternative View: Composite Distance Minimization In contrast to vertex- or edge-rooted searches, this paper introduces a different perspective based on minimizing a metric that couples shortest path distances with cycle lengths. This allows for a vertex-centric iterative approach inspired by Dijkstra’s algorithm. Definition 1 (Composite Distance) . For a vertex x\in V and a cycle c\in\mathscr{C} , the distance from x to c is d(x,c)=\min_{y\in\text{vertices}(c)}d(x,y) . The composite distance from vertex x to cycle c is defined as: d^{+}(x,c)=d(x,c)+\ell(c). (2) The composite distance from vertex x to the family of all cycles \mathscr{C} is: d^{+}(x)=\min_{c\in\mathscr{C}}d^{+}(x,c). (3) This definition shifts the focus from finding a cycle directly to finding a vertex x that minimizes this composite distance d^{+}(x) . The following theorem establishes the equivalence between minimizing d^{+}(x) and finding the MWC. Theorem 1 (Equivalence to MWC) . Minimizing d^{+}(x) over x\in V is equivalent to finding the length of the minimum weight cycle in G . Moreover, the minimum value \min_{x\in V}d^{+}(x) equals \ell(c^{*}) for any MWC c^{*} , and this minimum is attained for any vertex x\in\text{vertices}(c^{*}) . Proof. For any x\in V and c\in\mathscr{C} , d^{+}(x,c)=d(x,c)+\ell(c)\geq\ell(c) since d(x,c)\geq 0 . Equality d^{+}(x,c)=\ell(c) holds if and only if d(x,c)=0 , i.e. x\in\text{vertices}(c) .