3
$\begingroup$

The transformation replacing an edge by a graph gadget is widely used in graph theory.

As an example, in an answer Marzio De Biasi subdivided edges which increases the girth while preserving GI.

A gadget $GA$ is a graph with two distinguished vertices $u,v$.

The transformation $G,GA \to G'$ is: replace edge $(x,y)$ in $G$ by a copy of the gadget $GA$ and in the copy set $u=x,v=y$ so $x,y$ from the original graph are the same in all copies.

Which gadgets $GA$ preserve isomorphism: $G \cong H \iff G' \cong H'$

Added to clarify

I am looking for an algorithm given $GA,u,v$ to decide if it preserves isomorphism or not (reductions to GI complete problems are allowed though better be avoided).

Added 2 I am interested when $GA$ is fixed (and possibly small).

$\endgroup$
7
  • $\begingroup$ marziodebiasi[at]gmail.com. Furthermore, this is a possible idea to prove that given $GA, u, v$, deciding if $GA$ preserves isomorphism is $GI$-complete: Given $G_1 = (V_1, E_1), G_2 = (V_2, E_2)$ build $GA$ in the following way: start adding four nodes $u,v,x,y$ and edges $(u,x),(x,y),(y,v)$, then add an edge from $x$ to all the nodes of $V_1$, and an edge from $y$ to all the nodes of $V_2$. I'll think more about it, after lunch :-) $\endgroup$ Jun 23, 2014 at 10:45
  • $\begingroup$ @MarzioDeBiasi Will edit. Assume $GA$ is small and fixed. $\endgroup$
    – joro
    Jun 23, 2014 at 10:46
  • $\begingroup$ As sketched above, if the input of your decision problem (algorithm) is the triple $(GA,u,v)$, then the problem is GI-complete. If GA is fixed then the problem is obviously decidable in $O(1)$. $\endgroup$ Jun 23, 2014 at 12:12
  • 1
    $\begingroup$ @Marzio: If the OP is only interested in the case where GA is small, then an exponential-time algorithm would be practical. It's not clear to me that it's easy to find such an algorithm. $\endgroup$ Jun 23, 2014 at 12:31
  • $\begingroup$ @PeterShor: I think it's enough to test if $(X,u)\cup GA\cup (v,Y)$ is isomorphic to $(Y,u) \cup GA \cup (v,X)$; where $X$ is a star with a central node $x$ (connected to $u$ of GA) and $n$ neighbours (with $n > maxdeg(GA)$) and $Y$ is a star with a central node $y$ (connected to $v$ of GA) and $n+1$ neighbours. $\endgroup$ Jun 23, 2014 at 12:45

1 Answer 1

1
$\begingroup$

Just a summary of my (very informal / wrong?) comments/ideas above:

Every connected gadget $GA$ with two or more nodes, that doesn't introduce an asymmetry between $u$ and $v$ should be fine. In other words suppose $maxdeg(GA)=n$, and that $X$ is a star with a central node $x$ and $n+1$ leaves, $Y$ is a star with a central node $y$ and $n+2$ leaves.

The $GA$ preserves isomorphism if and only if the two graphs $X \cup GA \cup Y$, in which $x$ is replaced with $u$ and $y$ is replaced with $v$, is isomorphic to the graph $Y \cup GA \cup X$ in which $y$ is replaced with $u$ and $x$ is replaced with $v$.

This construction can also be used to check if a small fixed $GA$ preserves isomorphism.

Furthermore, the problem of deciding if $(GA,u,v)$ preserves isomorphism is GI-complete: given two graphs $G_1,G_2$; build the following gadget $GA$: add 4 new nodes $u,x,y,v$ and edges $(u,x),(x,y),(y,v)$, then add an edge from $x$ to all the nodes of $G_1$ and an edge from $y$ to all the nodes of $G_2$. $G_1,G_2$ are isomorphic if and only if $GA$ preserves isomorphism.

$\endgroup$
2
  • $\begingroup$ Thanks. I think gadgets exist for which G' and H' are isomorphic while G and H are not. Specific counterexample with u=0,v=1 and edges: [(0, 2), (0, 4), (0, 6), (1, 3), (1, 5), (1, 7), (2, 4), (2, 6), (3, 5), (3, 7), (4, 6), (5, 7)]. It satisfies your answer I believe. $\endgroup$
    – joro
    Jun 23, 2014 at 13:32
  • $\begingroup$ Lol, you might be correct. The gadget is disconnected, didn't notice this. I thought about your approach, but the faulty gadget confused me :( Isn't your approach a special case of GI which preserves (non-proper) coloring ? $\endgroup$
    – joro
    Jun 23, 2014 at 13:50

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.