<p>This is a standard minimum-cost circulation problem.  Give each directed edge capacity $1$ and cost $-1$.  Then a feasible circulation is a sum (ie, union) of edge-disjoint directed cycles, and the cost of the circulation is the negation of the number of edges.</p>

<p>Because all the costs and capacities are bounded by constants, a simple cycle-cancelling algorithm will find the required circulation in polynomial time.  This is <em>almost</em> the same as the obvious greedy algorithm:</p>

<pre><code>while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges
</code></pre>

<p>Here, the cost of a cycle is the sum of the costs of its edges.  Negative-cost cycles can be found using the Bellman-Ford shortest-path algorithm in $O(VE)$ time.  Each iteration reduces the cost of the current circulation by at least 1.  The initial (empty) circulation has cost $0$, and the final circulation has cost at least $-E$.  Thus, the algorithm ends after at most $E$ iterations, so its total running time is at most $O(VE^2)$.</p>

<p>This is not the fastest algorithm known.</p>

CC BY-SA 3.0
2012-04-16T04:04:17.233Z
think this works as long as a person does not want to work in more than one "unit", right? using phrasing of original question. but if people want to work in more than one unit, suspect this abstraction breaks down. OP stated problem in terms of only one unit, but this seems rather artificially constricting to me. [what human has only one preference...?]
vzn
CC BY-SA 3.0
2012-04-16T06:58:11.250Z
What is a "person" and a "unit"? This is a question about graphs.
Jeffε
CC BY-SA 3.0
2012-04-16T10:41:31.723Z
I am puzzled: Is my example not a counter example for this algorithm? After choosing C, the cycles C_1 and C_2 are no cycles anymore (because each cycles has one reversed edge); C won't be used again because it has positive cost after reversing its edges and there are no new cycles introduced. Are we talking about the same problem? Would love to have a mathematical formulation of the problem.
FiB
CC BY-SA 3.0
2012-04-16T13:45:11.990Z
After choosing (and reversing) $C$, removing the edges of $C$ shared by $C_1$ and $C_2$ leaves one long directed cycle $C'$.  Choosing (and reversing) $C'$ yields the same result as just choosing $C_1$ and $C_2$ from the beginning.  (In short, $C' = C_1 + C_2 - C$.)  Also: my answer _is_ a mathematical formulation of the problem!
Jeffε
CC BY-SA 3.0
2012-04-16T15:14:30.233Z
apparently a "unit" is something like a "department" and users are recording requests for transfers between departments [not exactly specific positions in the departments]? FIBs diagram seems to have units as vertices and edges as empl requests between units. FiB-- "would love to have a mathematical formulation of the problem".. it is really up to you to provide a precise formulation.. you seem to be halfway there..
vzn
CC BY-SA 3.0
2012-04-17T20:22:23.867Z
OK, I'll ask: Which is the fastest algorithm known?
Radu GRIGore
CC BY-SA 3.0
2012-04-19T21:53:13.040Z
@JɛﬀE, have you seen Radu_Grigore's answer? What do you think?
motobói
CC BY-SA 3.0
2012-04-20T12:57:31.910Z
@motobói, I think JɛﬀE answers your question very well. My answer is about a more general problem. I posted it for two reasons: (1) it seems reasonable that some employees might say "I want to go to A _or_ B" so the generalization seems to make sense for your problem, and (2) there is an implementation you could use.
Radu GRIGore
CC BY-SA 3.0
2012-04-20T22:03:17.767Z
@JɛﬀE, what if a user has priority over another? Say A and B both wants to change Detp. 1 for Dept. 2. But there is only one vacancy there. We have gave users a priority score, based on some internal metrics. Would that be as simple as using Cost = -Score
motobói
CC BY-SA 3.0
2012-04-15T20:12:35.173Z
2012-04-15T20:12:35.173Z
Jeffε
<p>This greedy approach will not always give the best solution.</p>

<p>Consider a cycle $C$ with $n$ edges $\{(v_1, v_2),\dots,(v_n,v_1)\}$ and two disjoint cycles $C_1$ and $C_2$ each having $n-1$ edges and sharing one edge with $C$.</p>

<p>If you use the largest cycle $C$ first, you can make $n$ employees happy. Then the cycles $C_1$ and $C_2$ each lose one edge and are no cycles anymore.</p>

<p>But if you choose $C_1$ and $C_2$, you can make $2(n-1)=2n-2$ employees happy.</p>

<p>Aside: Instead of adding two cycles in the above example, you could add $\lfloor\frac{n}{2}\rfloor$ cycles which makes the greedy solution even worse.</p>

CC BY-SA 3.0
2012-04-15T11:24:05.830Z
2012-04-15T15:45:09.427Z
2012-04-15T15:45:09.427Z
FiB
<p>there is probably a graph theory way/formulation to solve this, but this problem sounds more like a permutation problem to me where some of all permutations are rejected and others are valid. the permutations are employees and the positions are "positions" in the company. a permutation is rejected if it doesnt fit the requirements of "person [x] wants position [y]". the distinction of units/depts/org boundaries is apparently somewhat superfluous to the solution in this case.</p>

<p>this type of permutation problem with constraints can be readily converted into a instance of SAT (satisfiability) problem. the boolean variable assignments represent employees, and the constraint clauses represent the "person [x] wants position [y]" constraints. there are nearby classic examples of this, one usually called the "dinner table" problem where you have seating positions and guests and not all guests want to sit next to each other (or very similarly some guests want to sit next to other guests). </p>

<p>and of course there are sophisticated SAT solvers for fairly large instances involving roughly up to hundreds of variables and clauses, on PC, and if the problem is not "hard", in the thousands.</p>

<p>see eg [1] for a professional reference and [2] for a class exercise. there is also some structural similarity to what are known as "pigeonhole problems" which are well studied in SAT circles where pigeons are assigned to pigeonholes and you have more or less holes than pigeons. in that case however the pigeons are generally seen as interchangeable. in other words the dinner table problem is like the pigeonhole problem with stronger constraints and the guests/pigeons have required preferences.</p>

<p>note of course/keep in mind that for these types of problems, depending on the constraints the answer may be "no such constrained solution exists".</p>

<p>[1] <a href="http://www.springerlink.com/content/h488427215471887/" rel="nofollow">the dinner table algorithm, by crato</a></p>

<p>[2] <a href="http://www.cs.princeton.edu/courses/archive/fall04/cos402/assignments/satisfaction/index.html" rel="nofollow">CS402 princeton HW SAT</a></p>

<p>[3] <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow">Satisfiability problem, wikipedia</a></p>

CC BY-SA 3.0
2012-04-16T04:35:20.343Z
I tried the permutation using trademaximizer. Set a employee as a user wanting to trade his unit _X_ for unit _Y_. But the software won't allow more than one user trading the same item (his unit). Each item has to be unique. To accommodate this, I would had had to have, say, [(Jones) wants to trade Unit-C-James for Unit-D-Laura or Unit-D-Sergio or Unit-D-Mary]
motobói
CC BY-SA 3.0
2012-04-15T15:19:56.900Z
2012-04-15T15:19:56.900Z
vzn
<p>OK, I read the code of TradeMaximizer and I believe it solves the following, more general problem.</p>

<blockquote>
  <p>PROBLEM: Given is a directed graph whose arcs have costs. Find a set of vertex-disjoint cycles that maximizes the number of covered vertices first, and minimizes the total cost second.</p>
</blockquote>

<p>To solve the question asked here, make the vertices be employees and draw an arc $x\to y$ of unit cost when $x$ would like the job of $y$. Note that employees are now vertices rather than edges. The nice thing is that an employee can say "I really want the job of $y$, but that of $z$ would do too".</p>

<p>Solution:</p>

<ol>
<li><p>Build a bipartite graph as follows: For each vertex $x$ in the original graph introduce a left vertex $x_L$, a right vertex $x_R$, and an arc $x_L\to x_R$ whose cost is huge (bigger than the sum of costs in the original graph). For each arc $x\to y$ in the original graph, introduce an arc $x_L\to y_R$ in the bipartite graph.</p></li>
<li><p>Find a minimum cost perfect matching in the bipartite graph.</p></li>
</ol>

<p>There is some preprocessing of the original graph too: Remove arcs between SCCs, then process all SCCs of size $&gt;1$ as indicated above.</p>

<p>(In fact, TradeMaximizer iterates over all optimal solutions, according to the two criteria above, in order to heuristically optimize other things, such as the length of the biggest cycle. Big cycles increase the chance of a "deal" not going thru because one person changes their mind.)</p>

<p>PS: The author, Chris Okasaki, confirmed that this is what the code does, back at the <a href="http://okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html">blog post</a>.</p>

CC BY-SA 3.0
2012-04-17T06:58:51.687Z
I managed to find a solution to the original problem using TradeMaximizer. I'll post detais tomorrow.
motobói
CC BY-SA 3.0
2012-04-17T08:02:32.103Z
@motobói, but all you need to do is what I wrote in the second paragraph ...
Radu GRIGore
CC BY-SA 3.0
2012-04-19T20:06:52.673Z
I found this explanation about the algorithm: http://boardgamegeek.com/wiki/page/TradeMaximizer
motobói
CC BY-SA 3.0
2012-04-23T04:20:11.483Z
Could you explain or point to a explanation on why is necessary to remove arcs between Strong Comnected Components?
motobói
CC BY-SA 3.0
2012-04-23T09:58:55.040Z
@motobói, It is an optimization (for the average case). Steps (1) and (2) should be sufficient.
Radu GRIGore
CC BY-SA 3.0
2012-04-23T13:59:27.113Z
Ok, I'll mark this as the answer. What do you think?
motobói
CC BY-SA 3.0
2012-04-23T19:00:00.467Z
@motobói, Of course I'm happy if I helped, but which answer you accept should be entirely your decision. :)
Radu GRIGore
CC BY-SA 3.0
2012-04-16T15:59:56.150Z
2012-04-17T08:13:40.003Z
2012-04-17T08:13:40.003Z
Radu GRIGore
<p>I am not a computer science theorist, but think this real world problem belongs here.</p>

<h1>The problem</h1>

<p>My company have several units accross the country.</p>

<p>We offered to employees the possibility to work on another unit. But there is a condition: The total number of workers on a unit cannot change.</p>

<p>That means: We'll allow a employee to left his unit if someone wants his place.</p>

<p>Example (ficticious) request data:</p>

<pre><code>Name            Origin    Destination
Maria              1  -&gt;  2
Marcos             2  -&gt;  3
Jones              3  -&gt;  4
Terry              4  -&gt;  5
Joe                5  -&gt;  6
Rodrigo            6  -&gt;  1
Barbara            6  -&gt;  1
Marylin            1  -&gt;  4
Brown              4  -&gt;  6
Benjamin           1  -&gt;  3
Lucas              4  -&gt;  1
</code></pre>

<p>The above, plotted:
<img src="https://i.sstatic.net/FS8Gc.png" alt="Visualization of the above data"></p>

<p>See how we have to choose between the red, blue or black options?</p>

<p>The real problem is a little more complex, because we have 27 units and 751 requests. <a href="http://arborjs.org/halfviz/#/MjExNw" rel="noreferrer">Please take a look at the visualization</a> </p>

<h1>The goal</h1>

<p>Having collected all the requests, how to satisfy most of them?</p>

<h1>Theory(?) application</h1>

<p>Having graph $G(V, E)$, let every unit be a vertex $V$ and a request be a directed edge $E$, a successful exchange will take the form of a directed cyle.</p>

<p>Each cycle must use $E$ only once (<em>a worker cannot leave his unit twice</em>), but can visit $V$ several times (<em>a unit can have many workers wanting to leave</em>).</p>

<h2>The question</h2>

<p>If this problem is expressed as</p>

<blockquote>
  <p>"How to find the cycles which, together, involve the biggest number of
  non-shared edges in a directed graph"?</p>
</blockquote>

<p>Will we satisfy most of the requesters?</p>

<p>That being true, there is an algorithm to find that optimal set of cycles?</p>

<p>Will this greddy approach solve the problem?</p>

<ol>
<li>Find the biggest directed cycle on $G$;</li>
<li>Remove it's edges from $G$;</li>
<li>Repeat 1 until there is not a directed cycle on $G$;</li>
</ol>

<h2>Can you help me?</h2>

<p>Do you know another way to describe the original problem (making most of requesters happy)?</p>

<p><strong>Edit</strong>: changed department to unit, to better describe the problem.</p>

CC BY-SA 3.0
2012-04-15T06:12:22.743Z
So you want to find as many disjoint cycles in a graph as possible ?
Suresh Venkat
CC BY-SA 3.0
2012-04-15T07:12:20.407Z
Well, not sure about nomeclature. But what I need to do here is do the biggest number os exchanges. Which, for me, seems to translate to: find the cycles which, togheter, involve most edges.
motobói
CC BY-SA 3.0
2012-04-15T12:51:21.610Z
Are you sure that you just want to avoid using the same _edge_ more than once?  From your description of the application, it looks to me that you should avoid using the same _vertex_ more than once, which is a stronger condition.
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-15T14:36:59.433Z
Each edge represents a exchange requested by an employee. So, seems possible that two vertices are in two distinct cycles.
motobói
CC BY-SA 3.0
2012-04-15T15:55:32.660Z
@TsuyoshiIto: As I understand from the description, the condition is that at each vertex the indegree should be equal to the outdegree. So, vertex-disjointness is not needed.
Yoshio Okamoto
CC BY-SA 3.0
2012-04-15T16:15:58.170Z
By the way, if my understanding is correct, the problem should be solvable in polynomial time by means of network flow. Namely, if we give a unit of profit for a unit of flow along an edge, and we give a unit capacity on each edge, the problem is to find a circulation of maximum profit.
Yoshio Okamoto
CC BY-SA 3.0
2012-04-15T19:50:29.333Z
This post discusses a generalization of your problem http://okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html (think of each person as having one item to trade, namely their job placement).
Radu GRIGore
CC BY-SA 3.0
2012-04-15T20:32:05.127Z
I wish I could press up a thousand times, @RaduGRIGore.
motobói
CC BY-SA 3.0
2012-04-16T04:13:19.687Z
the blog post mentions this software [trademaximizer by okasaki](http://trademax.sourceforge.net/). wonder what algorithm it actually uses? scanning the site does not seem to turn up an answer. maybe in the source code...
vzn
CC BY-SA 3.0
2012-04-16T13:33:32.347Z
motobói, @Yoshio: Oops, I misinterpreted the diagram.  Now I agree that vertex-disjointness is not needed.  Thanks.
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-16T15:09:26.433Z
rough take on formulating/modeeling this (correct me if Im wrong). depts are sets of empls. empls currently belong to a single dept ie dept membership is disjoint. empls record requests to transfer to other depts. not all empls have requested transfers. problem: create a "shuffling" (permutation of some subset of all employees that have requests) that maximizes the total # of fulfilled requests.
vzn
CC BY-SA 3.0
2012-04-16T15:31:55.407Z
another idea for visualizing this: its similar to the "musical chairs" game across departments except that a chair is not removed and multiple cycles (or "subgames") are involved. the algorithm must try to find the biggest "subgames". the idea of permutations is not so relevant because people only move one "chair" at a time. however, presumably the algorithm is rerun periodically ie requests continue to come in after the last reordering.
vzn
CC BY-SA 3.0
2012-04-16T16:15:11.983Z
Awesome question, makes us feels like what we do can really be used in real life :).
Gopi
CC BY-SA 3.0
2012-04-16T17:54:56.510Z
I have edited to clarify the question.
motobói
CC BY-SA 3.0
2012-04-16T20:59:16.980Z
@motobói: The update is much clearer, except the question "See how we have to choose between the red, blue, and black options?"  No, I don't see.  Only the red option is a cycle; the blue and black options are just paths; moving employees along a path reduces the number at one end and increases the number at the other, violating the constraint that the number of employees at each department must not change.  (Are some edges in your figure meant to have multiple colors?)
Jeffε
CC BY-SA 3.0
2012-04-16T21:35:49.463Z
@motobói this is irrelevant to your question but I hope you can help. Now I am looking for visualization tools that can draw huge directed graph (with no. of edges is up to millions). I notice that you use arborjs for the visualization. Can it serve my purpose? Are you aware of any alternatives, thanks.
sma
CC BY-SA 3.0
2012-04-16T23:00:34.787Z
See this Stackoverflow thread, @pegausbupt: http://stackoverflow.com/questions/7034/graph-visualization-code-in-javascript
motobói
CC BY-SA 3.0
2012-04-17T08:10:55.300Z
@Gopi, a problem that is even more general than the one TradeMaximizer solves (you also have a bound on cycle length) is used to find transplant donors and _actually_ save lives.
Radu GRIGore
<ds.algorithms><graph-algorithms><application-of-theory>
How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?
motobói
# How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?

(Asked by: username_0 on 2012-04-15)

I am not a computer science theorist, but think this real world problem belongs here.
The problem
My company have several units accross the country.
We offered to employees the possibility to work on another unit. But there is a condition: The total number of workers on a unit cannot change.
That means: We'll allow a employee to left his unit if someone wants his place.
Example (ficticious) request data:
Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

The above, plotted:

See how we have to choose between the red, blue or black options?
The real problem is a little more complex, because we have 27 units and 751 requests. Please take a look at the visualization 
The goal
Having collected all the requests, how to satisfy most of them?
Theory(?) application
Having graph $G(V, E)$, let every unit be a vertex $V$ and a request be a directed edge $E$, a successful exchange will take the form of a directed cyle.
Each cycle must use $E$ only once (a worker cannot leave his unit twice), but can visit $V$ several times (a unit can have many workers wanting to leave).
The question
If this problem is expressed as

"How to find the cycles which, together, involve the biggest number of
  non-shared edges in a directed graph"?

Will we satisfy most of the requesters?
That being true, there is an algorithm to find that optimal set of cycles?
Will this greddy approach solve the problem?

Find the biggest directed cycle on $G$;
Remove it's edges from $G$;
Repeat 1 until there is not a directed cycle on $G$;

Can you help me?
Do you know another way to describe the original problem (making most of requesters happy)?
Edit: changed department to unit, to better describe the problem.

**Tags:** ds.algorithms, graph-algorithms, application-of-theory
> **Comments:**
> **username_1**: So you want to find as many disjoint cycles in a graph as possible ?  
> **username_0**: Well, not sure about nomeclature. But what I need to do here is do the biggest number os exchanges. Which, for me, seems to translate to: find the cycles which, togheter, involve most edges.  
> **username_2**: Are you sure that you just want to avoid using the same _edge_ more than once?  From your description of the application, it looks to me that you should avoid using the same _vertex_ more than once, which is a stronger condition.  
> **username_0**: Each edge represents a exchange requested by an employee. So, seems possible that two vertices are in two distinct cycles.  
> **username_3**: @TsuyoshiIto: As I understand from the description, the condition is that at each vertex the indegree should be equal to the outdegree. So, vertex-disjointness is not needed.  
> **username_3**: By the way, if my understanding is correct, the problem should be solvable in polynomial time by means of network flow. Namely, if we give a unit of profit for a unit of flow along an edge, and we give a unit capacity on each edge, the problem is to find a circulation of maximum profit.  
> **username_4**: This post discusses a generalization of your problem http://okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html (think of each person as having one item to trade, namely their job placement).  
> **username_0**: I wish I could press up a thousand times, @RaduGRIGore.  
> **username_5**: the blog post mentions this software [trademaximizer by okasaki](http://trademax.sourceforge.net/). wonder what algorithm it actually uses? scanning the site does not seem to turn up an answer. maybe in the source code...  
> **username_2**: motobói, @Yoshio: Oops, I misinterpreted the diagram.  Now I agree that vertex-disjointness is not needed.  Thanks.  
> **username_5**: rough take on formulating/modeeling this (correct me if Im wrong). depts are sets of empls. empls currently belong to a single dept ie dept membership is disjoint. empls record requests to transfer to other depts. not all empls have requested transfers. problem: create a "shuffling" (permutation of some subset of all employees that have requests) that maximizes the total # of fulfilled requests.  
> **username_5**: another idea for visualizing this: its similar to the "musical chairs" game across departments except that a chair is not removed and multiple cycles (or "subgames") are involved. the algorithm must try to find the biggest "subgames". the idea of permutations is not so relevant because people only move one "chair" at a time. however, presumably the algorithm is rerun periodically ie requests continue to come in after the last reordering.  
> **username_6**: Awesome question, makes us feels like what we do can really be used in real life :).  
> **username_0**: I have edited to clarify the question.  
> **username_7**: @motobói: The update is much clearer, except the question "See how we have to choose between the red, blue, and black options?"  No, I don't see.  Only the red option is a cycle; the blue and black options are just paths; moving employees along a path reduces the number at one end and increases the number at the other, violating the constraint that the number of employees at each department must not change.  (Are some edges in your figure meant to have multiple colors?)  
> **username_8**: @motobói this is irrelevant to your question but I hope you can help. Now I am looking for visualization tools that can draw huge directed graph (with no. of edges is up to millions). I notice that you use arborjs for the visualization. Can it serve my purpose? Are you aware of any alternatives, thanks.  
> **username_0**: See this Stackoverflow thread, @pegausbupt: http://stackoverflow.com/questions/7034/graph-visualization-code-in-javascript  
> **username_4**: @Gopi, a problem that is even more general than the one TradeMaximizer solves (you also have a bound on cycle length) is used to find transplant donors and _actually_ save lives.  

---

## 4 answers

### Answer by username_4 on 2012-04-16. Score: 9 | Accepted answer

OK, I read the code of TradeMaximizer and I believe it solves the following, more general problem.

> PROBLEM: Given is a directed graph whose arcs have costs. Find a set of vertex-disjoint cycles that maximizes the number of covered vertices first, and minimizes the total cost second.

To solve the question asked here, make the vertices be employees and draw an arc $x\to y$ of unit cost when $x$ would like the job of $y$. Note that employees are now vertices rather than edges. The nice thing is that an employee can say "I really want the job of $y$, but that of $z$ would do too".

Solution:

1. Build a bipartite graph as follows: For each vertex $x$ in the original graph introduce a left vertex $x\_L$, a right vertex $x\_R$, and an arc $x\_L\to x\_R$ whose cost is huge (bigger than the sum of costs in the original graph). For each arc $x\to y$ in the original graph, introduce an arc $x\_L\to y\_R$ in the bipartite graph.
2. Find a minimum cost perfect matching in the bipartite graph.

There is some preprocessing of the original graph too: Remove arcs between SCCs, then process all SCCs of size $>1$ as indicated above.

(In fact, TradeMaximizer iterates over all optimal solutions, according to the two criteria above, in order to heuristically optimize other things, such as the length of the biggest cycle. Big cycles increase the chance of a "deal" not going thru because one person changes their mind.)

PS: The author, Chris Okasaki, confirmed that this is what the code does, back at the [blog post](http://okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html).

> **Comments:**
> **username_0**: I managed to find a solution to the original problem using TradeMaximizer. I'll post detais tomorrow.  
> **username_4**: @motobói, but all you need to do is what I wrote in the second paragraph ...  
> **username_0**: I found this explanation about the algorithm: http://boardgamegeek.com/wiki/page/TradeMaximizer  
> **username_0**: Could you explain or point to a explanation on why is necessary to remove arcs between Strong Comnected Components?  
> **username_4**: @motobói, It is an optimization (for the average case). Steps (1) and (2) should be sufficient.  
> **username_0**: Ok, I'll mark this as the answer. What do you think?  
> **username_4**: @motobói, Of course I'm happy if I helped, but which answer you accept should be entirely your decision. :)  

---

### Answer by username_7 on 2012-04-15. Score: 23

This is a standard minimum-cost circulation problem.  Give each directed edge capacity $1$ and cost $-1$.  Then a feasible circulation is a sum (ie, union) of edge-disjoint directed cycles, and the cost of the circulation is the negation of the number of edges.
Because all the costs and capacities are bounded by constants, a simple cycle-cancelling algorithm will find the required circulation in polynomial time.  This is almost the same as the obvious greedy algorithm:
while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

Here, the cost of a cycle is the sum of the costs of its edges.  Negative-cost cycles can be found using the Bellman-Ford shortest-path algorithm in $O(VE)$ time.  Each iteration reduces the cost of the current circulation by at least 1.  The initial (empty) circulation has cost $0$, and the final circulation has cost at least $-E$.  Thus, the algorithm ends after at most $E$ iterations, so its total running time is at most $O(VE^2)$.
This is not the fastest algorithm known.

> **Comments:**
> **username_5**: think this works as long as a person does not want to work in more than one "unit", right? using phrasing of original question. but if people want to work in more than one unit, suspect this abstraction breaks down. OP stated problem in terms of only one unit, but this seems rather artificially constricting to me. [what human has only one preference...?]  
> **username_7**: What is a "person" and a "unit"? This is a question about graphs.  
> **username_9**: I am puzzled: Is my example not a counter example for this algorithm? After choosing C, the cycles C_1 and C_2 are no cycles anymore (because each cycles has one reversed edge); C won't be used again because it has positive cost after reversing its edges and there are no new cycles introduced. Are we talking about the same problem? Would love to have a mathematical formulation of the problem.  
> **username_7**: After choosing (and reversing) $C$, removing the edges of $C$ shared by $C_1$ and $C_2$ leaves one long directed cycle $C'$.  Choosing (and reversing) $C'$ yields the same result as just choosing $C_1$ and $C_2$ from the beginning.  (In short, $C' = C_1 + C_2 - C$.)  Also: my answer _is_ a mathematical formulation of the problem!  
> **username_5**: apparently a "unit" is something like a "department" and users are recording requests for transfers between departments [not exactly specific positions in the departments]? FIBs diagram seems to have units as vertices and edges as empl requests between units. FiB-- "would love to have a mathematical formulation of the problem".. it is really up to you to provide a precise formulation.. you seem to be halfway there..  
> **username_4**: OK, I'll ask: Which is the fastest algorithm known?  
> **username_0**: @JɛﬀE, have you seen Radu_Grigore's answer? What do you think?  
> **username_4**: @motobói, I think JɛﬀE answers your question very well. My answer is about a more general problem. I posted it for two reasons: (1) it seems reasonable that some employees might say "I want to go to A _or_ B" so the generalization seems to make sense for your problem, and (2) there is an implementation you could use.  
> **username_0**: @JɛﬀE, what if a user has priority over another? Say A and B both wants to change Detp. 1 for Dept. 2. But there is only one vacancy there. We have gave users a priority score, based on some internal metrics. Would that be as simple as using Cost = -Score  

---

### Answer by username_9 on 2012-04-15. Score: 4

This greedy approach will not always give the best solution.

Consider a cycle $C$ with $n$ edges $\{(v\_1, v\_2),\dots,(v\_n,v\_1)\}$ and two disjoint cycles $C\_1$ and $C\_2$ each having $n-1$ edges and sharing one edge with $C$.

If you use the largest cycle $C$ first, you can make $n$ employees happy. Then the cycles $C\_1$ and $C\_2$ each lose one edge and are no cycles anymore.

But if you choose $C\_1$ and $C\_2$, you can make $2(n-1)=2n-2$ employees happy.

Aside: Instead of adding two cycles in the above example, you could add $\lfloor\frac{n}{2}\rfloor$ cycles which makes the greedy solution even worse.


---

### Answer by username_5 on 2012-04-15. Score: -3

there is probably a graph theory way/formulation to solve this, but this problem sounds more like a permutation problem to me where some of all permutations are rejected and others are valid. the permutations are employees and the positions are "positions" in the company. a permutation is rejected if it doesnt fit the requirements of "person [x] wants position [y]". the distinction of units/depts/org boundaries is apparently somewhat superfluous to the solution in this case.

this type of permutation problem with constraints can be readily converted into a instance of SAT (satisfiability) problem. the boolean variable assignments represent employees, and the constraint clauses represent the "person [x] wants position [y]" constraints. there are nearby classic examples of this, one usually called the "dinner table" problem where you have seating positions and guests and not all guests want to sit next to each other (or very similarly some guests want to sit next to other guests).

and of course there are sophisticated SAT solvers for fairly large instances involving roughly up to hundreds of variables and clauses, on PC, and if the problem is not "hard", in the thousands.

see eg [1] for a professional reference and [2] for a class exercise. there is also some structural similarity to what are known as "pigeonhole problems" which are well studied in SAT circles where pigeons are assigned to pigeonholes and you have more or less holes than pigeons. in that case however the pigeons are generally seen as interchangeable. in other words the dinner table problem is like the pigeonhole problem with stronger constraints and the guests/pigeons have required preferences.

note of course/keep in mind that for these types of problems, depending on the constraints the answer may be "no such constrained solution exists".

[1] [the dinner table algorithm, by crato](http://www.springerlink.com/content/h488427215471887/)

[2] [CS402 princeton HW SAT](http://www.cs.princeton.edu/courses/archive/fall04/cos402/assignments/satisfaction/index.html)

[3] [Satisfiability problem, wikipedia](http://en.wikipedia.org/wiki/Boolean_satisfiability_problem)

> **Comments:**
> **username_0**: I tried the permutation using trademaximizer. Set a employee as a user wanting to trade his unit _X_ for unit _Y_. But the software won't allow more than one user trading the same item (his unit). Each item has to be unique. To accommodate this, I would had had to have, say, [(Jones) wants to trade Unit-C-James for Unit-D-Laura or Unit-D-Sergio or Unit-D-Mary]  

---

