AN ALGORITHM FOR DETECTING CYCLES IN UNDIRECTED GRAPHS USING CUDA TECHNOLOGY

Cycles count in a graph is an NP-complete problem. This work minimizes the execution time to solve the problem compared to the other traditional serial, CPU based one. It reduces the hardware resources needed to a single commodity GPU. We developed an algorithm to approximate counting the number of cycles in an undirected graph, by utilizing a modern parallel computing paradigm called CUDA (Compute Unified Device Architecture) from nVIDIA, using the capabilities of the massively parallel multi-threaded specialized processor called Graphics Processing Unit (GPU). The algorithm views the graph from combinatorial perspective rather than the traditional adjacency matrix/list view. The design philosophy of the algorithm shows that each thread will perform simple computation procedures in finite loop iterations to be executed in polynomial time. The algorithm is divided into two stages, the first stage is to extract a unique number of vertices combinations for a given cycle length using combinatorial formulas, and then examine whether given combination can for a cycle or not. The second stage is to approximate the number of exchanges (swaps) between vertices for each thread to check the possibility of cycle existence. An experiment was conducted to compare the results between the proposed algorithm and another distributed serial based algorithm based on the Donald Johnson backtracking algorithm.