Largest isomorphic subgraphs of two graphs with features

Question

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.

Thanks in advance!

Answer 1

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$.

Consequently, your problem is NP-hard, since it is at least as hard as a problem known to be NP-hard.

Your problem can be viewed as working with colored graphs. Typically, on practical instances, the colorings only make the problem easier, but from worst-complexity, the problem remains NP-hard.

If this is something you need to solve in a practical setting, one plausible approach is to formulate this as an instance of SAT and solve with an off-the-shelf SAT solver. It appears that the Glasgow Subgraph Solver supports induced subgraph isomorphism; I don't know whether it supports the colored version. You could also look at algorithms for subgraph isomorphism, such as these, to see if they can be extended to support induced subgraph isomorphism.