# How to build a set of closed chains with a sequence of different vertices?

I have a set of many bi-directional links like A-B, A-C, B-C, A-D, C-D, D-E, etc.

I need to find a set of many closed chains with a sequence of different vertices (vertex-disjoint cycles). It would be better if I can find them all.

How I solve the problem right now:

1. I build a directed graph by these links.
2. I take one of the vertices and then go to the others by edges, building walks.
3. I take the last walks' vertices one by one and then go to the others vertices except those that have already passed, continue building walks.
4. Repeat step 3 for each walk until I reach the start vertex. 4a. If other vertices are over and I could not build a closed chain, I delete the walk.

I apologize for my ignorance of graph theory. Perhaps I am reinventing the wheel? Perhaps there is already a solution to this issue? Please tell me.

• The directed graph may have unconnected islands of subgraphs.

What problems in my realization I want to solve:

1. I have to build many walks that will be deleted sooner or later because they are not closed chains.
2. I have to check which vertices have already been passed in order to get the next ones.

UPDATE

For what I want to apply it.

I need to filter out incoming incorrect currency pairs' data by their prices. Every currency pair has two current prices: (best) ask and (best) bid. The currency pair's data will be considered valid if it is possible to build an unprofitable exchanging closed chain (vertex-disjoint cycle) containing at least 4 vertices. (Cycle A-B-A is always valid.)

The closed chain is considered unprofitable when the product of the chain's asks is bigger than 1 and the product of the chain's bids is less than 1.

$$\prod A_i>1,$$

$$\prod B_i<1$$

In this case, each currency pair in the chain is valid.

At the same time, finding an invalid chain is not a consequence of the fact that the data is invalid. Only the failure to find a valid chain will be it.

• What is a "closed chain"? Do you mean a cycle? Is your question the following: given an undirected graph, find a set of vertex-disjoint cycles of maximum cardinality? – Yuval Filmus Nov 19 at 8:22
• @YuvalFilmus Yes, I mean a cycle. I do not know anything about maximum cardinality, but yes, it may be an undirected graph, and I want to find a set of vertex-disjoint cycles. If maximum cardinality helps to find a solution, good too. – Alex Shnaider Nov 19 at 8:57
• You need to define your question precisely. If you just want to find some collection of vertex-disjoint cycles, you can take the empty collection, or perhaps just one arbitrary cycle. I suppose you're after something more refined, but you'll have to tell us what exactly. – Yuval Filmus Nov 19 at 8:58
• @YuvalFilmus I want to find some collection of vertex-disjoint cycles. The larger the collection and the longer the cycle, the better. What do you mean by "take the empty collection"? – Alex Shnaider Nov 19 at 9:06
• The empty set is also a collection of vertex-disjoint cycles, and so solves your problem. In order to help you, we need to understand what you’re looking for. – Yuval Filmus Nov 19 at 9:07