So we have a graph with a small number of vertices (can be limited to as little as 20 if making this algorithm is hard). Lots of edges though, it is probably a 2 or at most 8 partite graph.

I'm looking for an algorithm that will take the edges of such a graph and split them up into cycles all of some specified size n. And by split them up I mean return a set of disjoint sets of edges, with every edge from the original graph in one of the returned sets.

This is for educational purposes (it's to help tell a story about Maryam Mirzakhani solving the problem of generating tripartite graphs that can be split into 5-cycles http://sharif.edu/~emahmood/papers/MR1366852English.pdf )


I'm not sure exactly what you are looking for, but Partitioning a Tripartite graph into Triangles (PTT) is NP-Hard, that is, there is no polynomial time algorithm capable of solving this problem unless P=NP. It seems that your problem is a generalization of PTT...

Hope this can help you. Let me know if this is not what you're looking for...


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.