  In a barter exchange market, agents bring items and seek to exchange their
items with one another. Agents may agree to a k-way exchange involving a cycle
of k agents. A barter exchange market can be represented by a digraph where the
vertices represent items and the edges out of a vertex indicate the items that
an agent is willing to accept in exchange for that item. It is known that the
problem of finding a set of vertex-disjoint cycles with the maximum total
number of vertices (MAX-SIZE-EXCHANGE) can be solved in polynomial time. We
consider a barter exchange where each agent may bring multiple items, and items
of the same agent are represented by vertices with the same color. A set of
cycles is said to be tropical if for every color there is a cycle that contains
a vertex of that color. We show that the problem of determining whether there
exists a tropical set of vertex-disjoint cycles in a digraph
(TROPICAL-EXCHANGE) is NP-complete and APX-hard. This is equivalent to
determining whether it is possible to arrange an exchange of items among agents
such that every agent trades away at least one item. TROPICAL-MAX-SIZE-EXCHANGE
is a similar problem, where the goal is to find a set of vertex-disjoint cycles
that contains the maximum number of vertices and also contains all of the
colors in the graph. We show that this problem is likewise NP-complete and
APX-hard. For the restricted case where there are at most two vertices of each
color (corresponding to a restriction that each agent may bring at most two
items), both problems remain NP-hard but are in APX. Finally, we consider
MAX-SIZE-TROPICAL-EXCHANGE, where the set of cycles must primarily include as
many colors as possible and secondarily include as many vertices as possible.
We show that this problem is NP-hard.

Data Structures and Algorithms;Computational Complexity