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

Question

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?

1. Find the biggest directed cycle on $G$;
2. Remove it's edges from $G$;
3. 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.

Answer 1

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.

Answer 2

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.

Answer 3

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 4

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

[2] CS402 princeton HW SAT

[3] Satisfiability problem, wikipedia