A homomorphism $f$ from a guest graph $G$ to a host graph $H$ is locally bijective, injective or surjective if for every $u\in V(G)$, the restriction of $f$ to the neighbourhood of $u$ is bijective, injective or surjective, respectively. The corresponding decision problems, LBHOM, LIHOM and LSHOM, are well studied both on general graphs and on special graph classes. Apart from complexity results when the problems are parameterized by the treewidth and maximum degree of the guest graph, the three problems still lack a thorough study of their parameterized complexity. This paper fills this gap: we prove a number of new FPT, W[1]-hard and para-NP-complete results by considering a hierarchy of parameters of the guest graph $G$. For our FPT results, we do this through the development of a new algorithmic framework that involves a general ILP model. To illustrate the applicability of the new framework, we also use it to prove FPT results for the Role Assignment problem, which originates from social network theory and is closely related to locally surjective homomorphisms.
翻译:从宾客图表到主机图的同质性美元是本地的双向、预测性或推测性美元,如果每1美元V(G)美元,将美元限制在一美元附近地区是双向的、预测性的或推测性的。相应的决定问题LBHOM、LiHOM和LSHOM在一般图表和特殊图表类别上都得到了很好的研究。除了在问题由宾客图表的树枝和最大程度参数参数参数参数参数参数化时产生的复杂结果之外,三个问题仍然缺乏对其参数化复杂性的透彻研究。本文填补了这一空白:我们通过考虑客机图的参数等级,证明了一些新的FPT、W[1]硬和准NP-完整的结果。关于我们的FPT结果,我们是通过开发一个新的算法框架来这样做的,该框架涉及一个普通的ILP模型。为了说明新框架的可适用性,我们还利用它来证明FPT的结果,因为FPT结果起源于社会网络和本地的同一型理论。