LBHOM

用于局部约束同构的算法框架

同构f从宾客图G到主机图H是局部的局部培养物，注射剂或弹性，如果对于每个U∈V（g），则F对U附近的F限制分别是生物，注射剂或过渡性。相应的决策问题LBHOM，LIHOM和LSHOM在一般图和特殊图形类别上都进行了很好的研究。除了通过宾客图的树宽和最大程度参数化的问题时，还会产生复杂性，这三个问题仍然缺乏对其参数化复杂性的彻底研究。本文填补了此差距：我们通过考虑访客图G的参数层次结构来证明许多新的FPT，W [1] -HARD和PARA-NP-COMPLETE结果。对于我们的FPT结果，我们通过开发涉及一般ILP模型的新算法框架来做到这一点。为了说明新框架的适用性，我们还使用它来证明角色分配问题的FPT结果，该问题源自社交网络理论，并且与本地透明的同型同态密切相关。