Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent
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 th...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2018-07-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3186/pdf |
| _version_ | 1797270064406200320 |
|---|---|
| author | Timothy Highley Hoang Le |
| author_facet | Timothy Highley Hoang Le |
| author_sort | Timothy Highley |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:20Z |
| format | Article |
| id | doaj.art-36399d74d4ba4697b1037434a30b0355 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:20Z |
| publishDate | 2018-07-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-36399d74d4ba4697b1037434a30b03552024-03-07T15:37:21ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502018-07-01vol. 20 no. 2Analysis of Algorithms10.23638/DMTCS-20-2-13186Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per AgentTimothy HighleyHoang LeIn 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.https://dmtcs.episciences.org/3186/pdfcomputer science - data structures and algorithmscomputer science - computational complexity |
| spellingShingle | Timothy Highley Hoang Le Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent Discrete Mathematics & Theoretical Computer Science computer science - data structures and algorithms computer science - computational complexity |
| title | Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent |
| title_full | Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent |
| title_fullStr | Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent |
| title_full_unstemmed | Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent |
| title_short | Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent |
| title_sort | tropical vertex disjoint cycles of a vertex colored digraph barter exchange with multiple items per agent |
| topic | computer science - data structures and algorithms computer science - computational complexity |
| url | https://dmtcs.episciences.org/3186/pdf |
| work_keys_str_mv | AT timothyhighley tropicalvertexdisjointcyclesofavertexcoloreddigraphbarterexchangewithmultipleitemsperagent AT hoangle tropicalvertexdisjointcyclesofavertexcoloreddigraphbarterexchangewithmultipleitemsperagent |