Timothy Highley ; Hoang Le - Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent

dmtcs:3186 - Discrete Mathematics & Theoretical Computer Science, July 31, 2018, vol. 20 no. 2 - https://doi.org/10.23638/DMTCS-20-2-1
Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per AgentArticle

Authors: Timothy Highley ; Hoang Le

    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.

    Volume: vol. 20 no. 2
    Section: Analysis of Algorithms
    Published on: July 31, 2018
    Accepted on: July 10, 2018
    Submitted on: March 10, 2017
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 990 times.
    This article's PDF has been downloaded 508 times.