Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 2
Cet article a éte moissonné depuis la source Episciences
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.
@article{DMTCS_2018_20_2_a1,
author = {Highley, Timothy and Le, Hoang},
title = {Tropical {Vertex-Disjoint} {Cycles} of a {Vertex-Colored} {Digraph:} {Barter} {Exchange} with {Multiple} {Items} {Per} {Agent}},
journal = {Discrete mathematics & theoretical computer science},
year = {2018},
volume = {20},
number = {2},
doi = {10.23638/DMTCS-20-2-1},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-1/}
}
TY - JOUR AU - Highley, Timothy AU - Le, Hoang TI - Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent JO - Discrete mathematics & theoretical computer science PY - 2018 VL - 20 IS - 2 UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-1/ DO - 10.23638/DMTCS-20-2-1 LA - en ID - DMTCS_2018_20_2_a1 ER -
%0 Journal Article %A Highley, Timothy %A Le, Hoang %T Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent %J Discrete mathematics & theoretical computer science %D 2018 %V 20 %N 2 %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-1/ %R 10.23638/DMTCS-20-2-1 %G en %F DMTCS_2018_20_2_a1
Highley, Timothy; Le, Hoang. Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 2. doi: 10.23638/DMTCS-20-2-1
Cité par Sources :