房屋市场是资源分配问题中研究最为广泛的模型之一。传统的房屋市场模型包括了n个参与节点和n个不可划分的资源,这些资源统称为物品。每个节点都持有其中一个物品,并对市场中的所有物品有一个优先级排序。房屋市场的相关问题主要是考虑在这样一个简单模型下,如何设计算法或是机制,有效利用排序信息,通过无金钱参与的交换,找到满足某些市场或是个人需求的分配。在本文中,我们主要研究了一个房屋市场变体模型中的物品可达性问题和最优可达分配问题。在这个变体模型中,所有节点都嵌入了一个网络中,并且只有网络中的邻居才能进行合法的交换。该变体由Gourvès等人首次提出,主要是考虑到现实房屋市场应用中节点间存在社交距离,节点之间大多数情况下是不存在直接的联系,或者是某些节点更愿意与邻近节点进行交换。在本文中,我们主要有两大贡献。首先,我们通过多项式算法的设计,对前面相关研究工作中留下的困难问题给出了肯定的回答。接着,我们从不同的网络和优先级排序,系统性地研究了变体模型中的物品可达性问题和最优可达分配问题。更具体地来说,我们通过对问题结构性质的探究,证明了路径上强排序下物品可达性等等问题可以归约到经典的2-SAT问题或者是路径寻找问题。由于2-SAT问题和路径寻找问题是多项式时间可解的,变体中的这些问题可以很有效地解决。但是,在另一方面,这些问题在网络或是优先级排序上即使只有部分改变,也会变成NP困难问题。我们通过从已知的NP完全问题,如2P1N-SAT问题和有向哈密尔顿路径问题,构造归约证明这些结果。在计算机领域,普遍认为NP困难问题不存在高效算法,除非P=NP。这些困难性结果上的差异也体现了网络和优先级排序对于房屋市场的重要影响。