Geodesic
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.

Voir la notice de l'article provenant de 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},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2018},
     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
PB  - mathdoc
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
%I mathdoc
%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. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-1/

Cité par Sources :