10
$\begingroup$

Given the graph G1, G2 and G3, we want to perform isomorphism test F between G1 and G2 as well as G1 and G3. If G2 and G3 are very similar such that G3 is formed by deleting one node and inserting one node from G2, and we have the result of F(G1,G2), can we compute F(G1,G3) without computing it from scratch by extending any existing state-of-the-art methods?

For example, if G2 is formed by nodes 2,3,4,5 and G3 is formed by nodes 3,4,5,6, can we make use of the result of F(G1,G2) to compute F(G1,G3) more efficiently?

$\endgroup$
6
$\begingroup$

This is a simple polynomial time reduction to show that the problem is GI complete: even if you know that $G_1, G_2$ are isomorphic, checking if $G_3$, built from $G_2$ deleting and adding a node, is isomorphic to $G_1$ is as hard as graph isomorphism itself (in the worst case).

Given two graphs $G = (V, E), G'= (V', E')$ build

$G_1 = ( V \cup V' \cup \{u\},\; E \cup E' \cup \{ (v_i,u) \mid v_i \in V \})$

i.e. the union of the two graphs plus an extra node $u$ connected to all the vertices of $V$

pick $G_2 = G_1$; and clearly they are isomorphic.

Now build $G_3$ deleting $u$ and adding $u'$ connected to all the vertices of $V'$:

$G_3 = ( V \cup V' \cup \{u'\},\; E \cup E' \cup \{ (v_i',u') \mid v_i' \in V'\} )$

$G_1, G_3$ are isomorphic iff $G, G'$ are isomorphic.

$\endgroup$
  • 2
    $\begingroup$ This is a nice reduction! However, I would add that GI-completeness alone doesn't necessarily mean there is no advantage, only that in the worst case their complexities are polynomially related. As another example, note that vertex-colored GI is also GI-complete, but most algorithms I know of can still take advantage of vertex colors in a useful way. $\endgroup$ – Joshua Grochow Jul 16 at 17:40
  • $\begingroup$ @JoshuaGrochow: thanks, I clarified that point. $\endgroup$ – Marzio De Biasi Jul 16 at 19:02
  • $\begingroup$ @MarzioDeBiasi: thank you for the explanations. Based on my understanding about your explanations, we can no take any advantage to compute F(G1,G3) knowing F(G1,G2) if the vertices connected to u and u' are different (not necessarily connected to all vertices of V or V') even if we know G and G' are isomorphic. Is that correct? In this case, is this problem as hard as the graph isomorphism itself? $\endgroup$ – Eric Huang Jul 17 at 3:06
  • $\begingroup$ @EricHuang: the reduction says that given two isomorphic graphs $G_1, G_2$ and an explicit way to build $G_3$ by deleting/adding one node (and some edges) to $G_2$ the problem of checking whether $G_1, G_3$ are isomorphic is as hard as graph isomorphism. BTW, this result also extends to the associated promise problem in which you're not given the explicit way to build $G_3$, but only the promise that $G_1,G_3$ are isomorphic up to a node delete/add operation. $\endgroup$ – Marzio De Biasi Jul 17 at 6:48
  • $\begingroup$ You may try the Weisfeiler-Lehman method or its variations, especially if your original graphs have structures like planar, tree, interval graph or bounded treewidth graph, their Weisfeiler-Lehman dimension is a small constant, in the refinement step, I guess you can take advantage of the relationship between the two graphs. $\endgroup$ – Rupei Xu Jul 29 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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