I’m trying to find an algorithm that can find the lengths of simple cycles in an undirected graph in parallel that benefits strongly enough from it’s parallelization to be practically more efficient than what I’m currently using to find simple cycles in an undirected graph.
Basically if a graph has n nodes, I need to know if there is a simple cycle of each possible length between 2 and n in the graph. I’m currently using https://www.boost.org/doc/libs/1_55_0/boost/graph/hawick_circuits.hpp because it performs massively better than any other implementation I’ve found of simple cycle algorithms. However, it seems that NP-hard graph problems that rely on backtracking tend to be very tricky to parallelize.
I have access to computers that would allow me to benefit greatly from distributing the problem across CPU cores, but I’m failing to find papers or past discussions of people parallelizing this particular problem space.