2
$\begingroup$

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!

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Perfect, thanks, I will look into this, I need to apply it in a practical setting, so I will look deeper into formulating it as a SAT instance! $\endgroup$ Jan 3, 2023 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.