# Largest isomorphic subgraphs of two graphs with features

the following question came up in a problem I am working on:

Suppose you have two graphs $$G_1=(V_1, E_1), G_2=(V_2,E_2)$$ that have features attached to them, i.e. to every $$v\in V_1$$ or $$v\in V_2$$ there is a vector $$w_v\in\mathbb R^n$$ with fixed $$n$$ of features mapped to, and similarly for all edges. We call two of these graphs isomorphic, if there exists a bijective function $$f: V_1\to V_2$$, such that $$uv\in E_1\Leftrightarrow f(u)f(v)\in E_2,$$ $$w_u=w_{f(u)}\text{ and}$$ $$w_{uv}=w_{f(u)f(v)}$$ for all $$u,v\in V_1$$.

Given such two graphs, what would be the best way to get the maximal isomorphic subgraphs, i.e. a subgraph of $$G_1$$ induced by a set of vertices $$U_1$$, such that there exists an injective $$f:U_1\to V_2$$ like above (with $$E_1, E_2$$ replaced by the appropriate induced edge sets) that has a maximal amount of vertices.

• That sounds very like a $\mathsf{NP}$-hard problem. Dec 30, 2022 at 12:56

This looks like it is at least as hard as the induced subgraph isomorphism problem. Suppose that all $$w$$ vectors are 0. Then your question is identical to asking whether for a maximal induced subgraph of $$G_1$$ that is isomorphic to an induced subgraph of $$G_1$$. The solution to your problem will be all of $$G_1$$ iff $$G_1$$ is isomorphic to an induced subgraph of $$G_2$$.