0
$\begingroup$

I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph.

In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-4, 1-3-4-5 and 1-2-3-4-5. The last cycle does not add any further information about the cyclic structure of my graph that's why I don not want to process it.

Example

I made few searches and found out there is the Edge Cycle Cover and finding the minimum is NP-HARD problem. I'm not sure if it is exactly what I'm looking for.

So, any help understanding this problem? Is there a heuristic to get only a subset of cycles for each vertex in the graph? it does not have to be minimal!

$\endgroup$
  • $\begingroup$ what is the condition for disregarding a cycle? You say the cover has not be minimal but it looks like you disregard cycle 1-2-3-4-5 because 1-3-4-5 and 1-2-3 (being both shorter!) provide the same information when considered together. Also, it does not seem to me you are looking for cycles, but transpositions (i.e., different paths between two different nodes), ... $\endgroup$ – Carlos Linares López Nov 23 '19 at 20:33
  • $\begingroup$ @CarlosLinaresLópez actually I would love to get the minimal cover, but as you said in my intuition I am thinking about shorter cycles. Maybe, I didn't formulate my question properly, but I am simply looking for a way to not process all the cycles in the graph because some cycles do not give more information about the graph structure, i.e. that are composed of edges already in previously processed cycles. So maybe looking for a cycle containing every edge in the graph would do the job? $\endgroup$ – PhiloJunkie Nov 23 '19 at 20:49
  • 1
    $\begingroup$ So do you want a small number of cycles that covers every edge? How does your problem differ? $\endgroup$ – Juho Nov 24 '19 at 8:22
  • $\begingroup$ @Juho That's what I want yup! It is the same as Minimum cover problem right? $\endgroup$ – PhiloJunkie Nov 24 '19 at 11:07
  • $\begingroup$ @Juho What I'm doing now is coloring my edges and checking for every non visited edge (not already part of previously found cycle/ colored gray) if it is part of a cycle. It will not give me the minimum cover but I find it simple and yet efficient way to get a cycle cover. $\endgroup$ – PhiloJunkie Nov 24 '19 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.