# A Multi-Threading Algorithm to Detect and Remove Cycles in Vertex- and Arc-Weighted Digraph
## 2 Related Work  
Many literatures have focused on the cycle detection of a directed/undirected graph. Hamiltonian cycle is a special cycle that covers each vertex exactly once. The decision problem of whether a graph contains Hamiltonian cycle is NP-complete, so [1] presents some conjectures. A non-recursive algorithm to detect Hamiltonian cycle is presented in [2], and this algorithm is applied to flow-shop scheduling problem.  
Another two important cycles are the shortest and longest cycles of a graph, because they decide the girth and diameter/circumference of a graph, respectively. An approximate algorithm is given in [3] to find the shortest cycle in an undirected unweighted graph, whose expected time complexity is between \(\mathrm{O}(nlogn)\) and \(\mathrm{o}(n^{2})\), where \(n\) is the number of vertices of a graph. The algorithm presented in [4] aims to find the shortest cycle for each vertex in a graph. In a non-Hamiltonian graph, the longest cycles through some special vertices are discussed in [5; 6; 7], where [5] focuses on the longest cycles through large degree vertices, while [6; 7] pay attention to the longest cycles passing all vertices of degree at least a given threshold.  
Besides characterizing or detecting special cycles of a graph, enumerating and counting cycles is also an important problem. Some explicit formulae for the number of 7-cycles in a simple graph are obtained in [8]. Recently, distributed algorithms to count or enumerate cycles are presented in [9], in order to solve this problem more efficiently.  
Sometimes a graph is dynamic, it grows by arc insertions. For this kind of graphs, the cycle detection problem is referred to as incremental cycle detection. Two online algorithms are presented in [10] to solve this problem, which handle \(m\) arc additions for \(n\) vertices in \(\mathrm{O}(m^{\frac{3}{3}})\) and \(\mathrm{O}(n^{\frac{5}{3}})\) time, respectively. The algorithms presented in [11] are designed for sparse and dense graphs, which take \(\mathrm{O}(\min\{m^{\frac{1}{2}},n^{\frac{2}{3}}\})\) and \(\mathrm{O}(n^{2}logn)\) time, respectively.  
Most of the above algorithms are based on DFS (Depth-First Search), which is inherently sequential [12], and they often cause out-of-memory exception when they are run on commodity PCs to solve large-scale graphs.  
Recently, many parallel and distributed graph-processing algorithms have been proposed. A message-passing algorithm is presented in [13] to count short cycles in a graph. The distributed cycle detection algorithm proposed in [14] is based on the bulk synchronous message passing abstraction, which is suitable for implementation in distribute graph processing systems. The cloud computing systems breed parallel graph processing platforms, such as Pregel [15], GraphX [16], and GPS [17]. These platforms are based on the BSP (Bulk Synchronous Parallel) model, which depends on costly distributed computing systems. Therefore, PCs cannot play to these algorithms' strengths.  
The purpose of this paper is to propose an algorithm of detecting and removing cycles of large-scale digraphs using a single commodity PC.