Algorithm to find most nodes in distinct cycles

Question

I am trying to design a program where people trade objects within a fixed set of objects. They offer a single product, and designate a set of products they are willing to accept for that product. The job of the program is to involve as many people in a trade as possible.

To do this, I create a directed graph, where each edge points from a person who will give a product to a person who wants that product.

I want to find the distinct cycles (they don't share a node) that cover the largest subset.

How would I do that?

• David Richerby: Your problem is very closely related to looking for disjoint cycle covers.
• Raphael: What have you tried and where did you get stuck? Do you know how to find any cycle?
• Nathan Merrill: @Raphael To find a cycle I would recursively follow each node, keeping a list of visited nodes, and if the neighbor has already been visiting, then my history is a cycle. Iterating through every possible set of cycles seems like the wrong way to go about it at that step, though.

Answer 1

Your problem is NP-complete (formulated as a decision problem), by reduction from SAT. For simplicity, I describe a reduction that uses self-loops, but they can easily be avoided.

Given an instance of SAT, create nodes for each variables and each clause. For each assignment of each variables, add directed cycles connecting the variable node with clause nodes satisfied by this assignment, for all possible such subsets (the empty subset corresponds to a self-loop). Since there are no parallel edges, we can also think of these cycles as resulting from a single cycle going through all satisfied clauses by taking all possible shortcuts not avoiding the variable node.

In the resulting graph, it is possible to cover all nodes of and only if the formula is satisfiable, completing the proof.

In practice, it might be possible to find good solutions heuristically, but that could depend on the nature of your instances.

• Raphael: Okay, but so what? The question asks for algorithms, so an expansion of the last paragraph is what Nathan needs. Maybe our reference question contains some useful pointers, but that's all very general.