1
$\begingroup$

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.

Additional information:

  • The set of links is about 10,000.
  • 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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Nov 19 at 8:22
  • $\begingroup$ @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. $\endgroup$ – Alex Shnaider Nov 19 at 8:57
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 19 at 8:58
  • $\begingroup$ @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"? $\endgroup$ – Alex Shnaider Nov 19 at 9:06
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 19 at 9:07

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.