论文标题
用于局部约束同构的算法框架
An Algorithmic Framework for Locally Constrained Homomorphisms
论文作者
论文摘要
从访客图$ g $到主机图$ h $的同构$ f $是本地bioxtive，Imentive或Sunfimive，如果对于v（g）$中的每一个$ u \，则分别对$ u $的$ f $的限制是$ u $的$ f $。相应的决策问题LBHOM，LIHOM和LSHOM在一般图和特殊图形类别上进行了很好的研究。除了通过宾客图的树宽和最大程度参数化的问题时，还会产生复杂性，这三个问题仍然缺乏对其参数化复杂性的彻底研究。本文填补了这一差距：我们通过考虑访客图$ g $的参数层次结构来证明许多新的FPT，W [1] -HARD和PARA-NP-COMPLETE结果。对于我们的FPT结果，我们通过开发涉及一般ILP模型的新算法框架来做到这一点。为了说明新框架的适用性，我们还使用它来证明角色分配问题的fpt结果，该问题源自社交网络理论，与当地的汇总同态密切相关。
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.
