The directed 3-Cycle cover asks for a vertex-covering set of oriented cycles with at least three vertices per cycle such that every vertex is covered by exactly one cycle.

I have scrutinzed the internet for some time for freely availabe benchmark problems but couldn't find anything useful.

So my question is where I can find such instances with known optimal solutions that were hard to find, resp., how such instances can be created.

The reason for asking is that I found a new algorithm for the problem and want to get a feeling about its quality and robustness.

  • $\begingroup$ Can't you just take any undirected graph and test if there is a 3-cycle cover? If my memory is not betraying me (it has been many years since I took graph theory), that can be done in polynomial time. Once you gather some graphs, you can test your algorithm (together with other algorithms) for robustness. sparse.tamu.edu has many sparse matrices that you can make into (un)directed graphs. $\endgroup$ – Abdullah Ali Sivas Jul 14 at 4:53
  • $\begingroup$ @AbdullahAliSivas sorry for replying so late. You remembered the fact that the existence of 3-cycle covers can be checked in polynomial time for undirected graphs via the reduction to matching by Tutte. For a directed graph the problem is in NP as soon as you restrict the lengths of the cycles from above or below and ruling out cycles of length two is such a restriction. $\endgroup$ – Manfred Weis Jul 23 at 14:56

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.