We study a simple exchange market, introduced by Gourv\'{e}s, Lesca and
Wilczynski (IJCAI-17), where every agent initially holds a single object. The
agents have preferences over the objects, and two agents may swap their objects
if they both prefer the object of the other agent. The agents live in an
underlying social network that governs the structure of the swaps: Two agents
can only swap their objects if they are adjacent. We investigate the REACHABLE
OBJECT problem, which asks whether a given starting situation can ever lead, by
means of a sequence of swaps, to a situation where a given agent obtains a
given object. Our results answer several central open questions on the
complexity of REACHABLE OBJECT. First, the problem is polynomial-time solvable
if the social network is a path. Second, the problem is NP-hard on cliques and
generalized caterpillars. Finally, we establish a three-versus-four dichotomy
result for preference lists of bounded length: The problem is easy if all
preference lists have length at most three, and the problem becomes NP-hard
even if all agents have preference lists of length at most four.

研究通过物品交换娱乐的市场，给定其社交网络结构及代理人的物品偏好列表，探讨给定的起始状态是否能够达到给定目标状态的问题，分别在路径、团和广义毛毡上回答了该问题的时间复杂度，并得出在有限偏好列表长度的情况下，该问题具有三对四的分解型结果。