Neighborhood-Preserving Mapping between Trees

摘要

We introduce a variation of the graph isomorphism problem, where, given two graphs G_1 = (V_1, E_1) and G_2 = (V_2, E_2) and three integers l, d, and k, we seek for a set D (∈) V_1 and a one-to-one mapping f : V_1 → V_2 such that ｜D｜ ≤ k and for every vertex v ∈ V_1 D and every vertex u ∈ N_(G_1)~l (v) D we have f(u) ∈ N_(G_2)~d (f(v)). Here, for a graph G and a vertex v, we use N_G~i (v) to denote the set of vertices which have distance at most I to v in G. We call this problem Neighborhood-Preserving Mapping (NPM). The main result of this paper is a complete dichotomy of the classical complexity of NPM on trees with respect to different values of l, d, k. Additionally, we present two dynamic programming algorithms for the case that one of the input trees is a path.