[Solved]: Finding trading cycles

ignougroup
Problem Detail: Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,

  • person 1 has item A, C, D, and wants item F
  • person 2 has item B, C, and wants E
  • person 3 has item E, and wants G …

You get the idea. So it’s basically a supply/demand matching problem, and if we represent this as a person-item matrix, it’s gonna be a very sparse one. So my question would be:

  1. How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?
  2. How do I find the shortest series (or path) that involves more than 2 people (so one-to-one exchange I think I’ve figured how by using some matrix operations)?
  3. What would be the complexity for finding longest/shortest paths?

Any advice would be appreciated.

Asked By : Shuai

Answered By : tjhighley

I’m assuming that items are always traded 1-for-1.

How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?”

If you are only looking for one long path, then you are looking for a Hamiltonian circuit if one exists, so the decision version of the problem is NP-complete. If you are open to having multiple disjoint cycles of exchange and just looking for as many items as possible involved in the exchange, then it is the MAX SIZE EXCHANGE problem from the Kidney Exchange literature, and it is solvable in polynomial time. P. Biro, D. F. Manlove, and R. Rizzi. Maximum weight cycle packing in directed graphs, with application to kidney exchange programs. Discrete Mathematics, Algorithms and Applications, 1(04):499–517, 2009.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64922  Ask a Question  Download Related Notes/Documents