Generate a directed graph with n cycles

Question

I want to generate a directed graph that contains exactly the specified amount of cycles with their respective length. For example, the graph should contain:

2 cycles of the size 3 
1 cycle of the size 5

• Does such an algorithm already exist? If not, what would be your approach to solving this problem? In detail, the following parameters are given:

  1. the number of vertices (e.g., 15)
  2. the number of components (e.g., 2)
  3. the cycles that have to be in the graph (e.g, {3-cycle, 3-cycle, 5-cycle})

• I only found several algorithms (e.g., Tarjan) that can detect cycles in existing graphs. Do you think it is possible to also use cycle detection algorithms to generate graphs with a specific amount of cycles?

Answer 1

A greedy algorithm that might fail on some cases, needs peer review.

Note that, if we have a cycle of some length k:

1 -> 2 -> 3 -> ... -> k -> 1

We can make another cycle of the same length by introducing a single other node:

1 -> 2 -> 3 -> ... -> k -> 1
k' -> 1 -> 2 -> ... -> k - 1 -> k'

Or a cycle of the same length - 1:

1 -> 2 -> 3 -> ... -> k -> 1
k' -> 1 -> ... -> k - 2 -> k'

This can go on forever by always introducing a new node and connecting it to two other nodes in an initial, big enough, cycle.

So, if you can afford an infinite number of nodes, just do this, starting from the largest cycle you need.

If you must work with a fixed number of nodes, we should strive to minimize the number of nodes used for constructing the requested cycles. Any leftover nodes can easily be added so they do not form any cycles.

Start with the largest cycle again:

1 -> 2 -> ... -> k -> 1

By not adding any more nodes, we can obtain from this the following:

1. k length 2 cycles: 2 -> 1, 3 -> 2, ... 1 -> k.

2. k - 2 length 3 cycles: 3 -> 1, 4 -> 2, ..., k -> k - 2.

3. In general, k - p + 1 length p cycles.

None of these will generate additional cycles. So the whole algorithm will be:

1. Build your largest requested cycle.

   1.1. If more than one largest, build more by adding a single new node for each. Note that this affects the procedure described for building smaller cycles out of a big one by not adding any new nodes, because you get a new cycle of a certain size. There will be some overlap, so you can't simply double the number of solutions. As far as I can tell, it only increases the number by 1.

2. Build your lesser cycles by not adding any new nodes.

3. If not done building the needed cycles:

   3.1. If you have nodes left, use them.

   3.2. If you don't have nodes left, output no solution.

4. If done building cycles:

   4.1. If you have nodes left, add them as a linked list somewhere so they won't bother you.

   4.2. If no nodes left, you're done.