<p>This is actually how many graph isomorphism algorithms work (often in combination with Weisfeiler-Lehman). For example, bounded color class isomorphism (Luks 1983) works by first finding isomorphisms within each color class, then combining those using the edges between color classes. Zemlyachenko's trick could then be used to individualize $\tilde{O}(\sqrt{n})$ vertices, so that the resulting graph had bounded color classes (which led to the previous-best algorithm for GI).</p>

<p>Babai's recent algorithm does another kind of divide-and-conquer that is sort of along the lines you mention. It either finds a partition of the graph into small parts (where "small" here means some constant fraction smaller than the original graph; the result is that such recursion can only happen $O(\log n)$ times) or finds a large embedded Johnson scheme. In the latter case, it handles the Johnson scheme by a different recursive technique, but then handles the vertices that aren't in the Johnson scheme essentially along the lines you suggest. (Indeed, if you look at the table of contents of Babai's paper you will see there is quite a lot of talk about "local to global" principles, though it's not really the same "local to global" you're talking about here.)</p>

CC BY-SA 3.0
2016-02-15T16:02:09.643Z
2016-02-15T16:02:09.643Z
Joshua Grochow
<p>NAUTY "colors" nodes with constant depth neighborhood canonical forms. Babai's new algo does likewise with log size neighborhoods.</p>

<p>The kicker is that in a random graph the diameter is about log n, so you end up gobbling the whole thing.</p>

<p>Definitely worth doing for sparse graphs, can really cut down the state space you need to search. Also when you have to go brute force, only check repeated prime cycles, not all k! <a href="https://oeis.org/A186202">https://oeis.org/A186202</a></p>

CC BY-SA 3.0
2016-02-12T22:19:33.217Z
Thanks for your response. I think I need to specify my question more, make it more precise, case based. I am trying to construct an algorithm(I have draft, in case you are interested) and to find similarities with existing algorithm. If I am not wrong, NAUTY not does not "Split"(informally saying) graph the way I have asked,
Michael
CC BY-SA 3.0
2016-02-12T23:07:06.633Z
There are a number of options you can pass for the vertex "coloring" phase. I think the default is vertex degree (depth 1 neighborhoods). That is what most splitting algorithms boil down to. A local subgraph around a vertex you can use as a certificate.
Chad Brewbaker
CC BY-SA 3.0
2016-02-12T23:31:19.507Z
"I think the default is vertex degree (depth 1 neighborhoods)" --probably this means  1 Dimensional  Weisfeiler-lehman method, in that case $K$  Dimensional  Weisfeiler-lehman((depth $K$  neighborhoods) is not what I meant for sure.  if $K=1$, then it can not handle  regular graph. You can "construct" graph that makes $K$  Dimensional  Weisfeiler-lehman ineffective, for example Cai-Furer-Immerman pair. Certainly  I do not mean that.Note that Nauty uses  1 Dimensional  Weisfeiler-lehman method.
Michael
CC BY-SA 3.0
2016-02-13T14:15:09.233Z
Yes, as part of the certificate you can color vertices with linear algebraic properties of their neighborhoods. Sometimes these break symmetries. If you come up with a vertex invariant you find useful for a class of graphs see section 10 on how to add it to NAUTY, http://pallini.di.uniroma1.it/nug25.pdf
Chad Brewbaker
CC BY-SA 3.0
2016-02-12T21:58:32.037Z
2016-02-12T21:58:32.037Z
Chad Brewbaker
<p>Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism?</p>

<p>For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq H$.</p>

<p>Now assume there exists an algorithm that splits graph $G$  in to  Subgraph  $G_1, G_2$(in $G$, $G_1$ and $G_2$ are connected through a  set of edges, say, $R_1$) and finds Isomorphism to corresponding graph $H_1 , H_2$(Local Isomorphism), then merge those Isomorphism to check whether $G\simeq H$ (Global isomorphism).</p>

<p>Does there exist such algorithm in Graph Isomorphism Literature ?</p>

<p><strong><em>EDIT:</em></strong></p>

<p>I apologize for a vague description, I should be more specific, but it is really hard to specify at the moment. For the time being, note that I do not mean a splitting based on vertex classification <strong>entirely</strong> or something like that.  An algorithm that is based on  <strong>$K$  Dimensional  Weisfeiler-lehman(depth $K$  neighborhoods) entirely</strong>,  is not what I meant, that is for sure**.  if $K=1$, then it can not handle  regular graph. You can "construct" graph that makes $K$  Dimensional  Weisfeiler-lehman ineffective, for example Cai-Furer-Immerman pair. Certainly  I do not mean that.Note that NAUTY  uses  1 Dimensional  Weisfeiler-Lehman method.</p>

<p><a href="https://cstheory.stackexchange.com/questions/21962/graph-isomorphism-given-a-partial-isomorphism">This question</a> is the closest I got to mine, but it does not answer  my query.</p>

CC BY-SA 3.0
2016-02-08T08:51:15.500Z
If the construction of a canonical labeling  falls into your question, then algorithms for bounded width (tree-width http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6979003 or rank-width http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7354440) or others based on graph decompositions (see the book by Martin Grohe) are such examples.
M. kanté
CC BY-SA 3.0
2016-02-08T16:15:36.100Z
it seems like any isomorphism algorithms that sort vertices based on degrees (a common design pattern in this area) are conceptually nearly of this type... they are attacking subgraph isomorphism for the subproblems associated with separate degrees...
vzn
CC BY-SA 3.0
2016-02-08T16:19:54.353Z
another direction is the [maximum common subgraph isomorphism problem](https://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem) where if the two graphs are same "size" and maximum common subgraph isomorphism is the same, the graphs are isomorphic.
vzn
<reference-request><graph-theory><graph-isomorphism>
Local Graph Isomorphism to construct Global Graph Isomorphism
Michael
# Local Graph Isomorphism to construct Global Graph Isomorphism

(Asked by: username_0 on 2016-02-07)

Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism?

For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq H$.

Now assume there exists an algorithm that splits graph $G$ in to Subgraph $G\_1, G\_2$(in $G$, $G\_1$ and $G\_2$ are connected through a set of edges, say, $R\_1$) and finds Isomorphism to corresponding graph $H\_1 , H\_2$(Local Isomorphism), then merge those Isomorphism to check whether $G\simeq H$ (Global isomorphism).

Does there exist such algorithm in Graph Isomorphism Literature ?

***EDIT:***

I apologize for a vague description, I should be more specific, but it is really hard to specify at the moment. For the time being, note that I do not mean a splitting based on vertex classification **entirely** or something like that. An algorithm that is based on **$K$ Dimensional Weisfeiler-lehman(depth $K$ neighborhoods) entirely**, is not what I meant, that is for sure\*\*. if $K=1$, then it can not handle regular graph. You can "construct" graph that makes $K$ Dimensional Weisfeiler-lehman ineffective, for example Cai-Furer-Immerman pair. Certainly I do not mean that.Note that NAUTY uses 1 Dimensional Weisfeiler-Lehman method.

[This question](https://cstheory.stackexchange.com/questions/21962/graph-isomorphism-given-a-partial-isomorphism) is the closest I got to mine, but it does not answer my query.

**Tags:** reference-request, graph-theory, graph-isomorphism
> **Comments:**
> **username_1**: If the construction of a canonical labeling  falls into your question, then algorithms for bounded width (tree-width http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6979003 or rank-width http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7354440) or others based on graph decompositions (see the book by Martin Grohe) are such examples.  
> **username_2**: it seems like any isomorphism algorithms that sort vertices based on degrees (a common design pattern in this area) are conceptually nearly of this type... they are attacking subgraph isomorphism for the subproblems associated with separate degrees...  
> **username_2**: another direction is the [maximum common subgraph isomorphism problem](https://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem) where if the two graphs are same "size" and maximum common subgraph isomorphism is the same, the graphs are isomorphic.  

---

## 2 answers

### Answer by username_3 on 2016-02-15. Score: 5

This is actually how many graph isomorphism algorithms work (often in combination with Weisfeiler-Lehman). For example, bounded color class isomorphism (Luks 1983) works by first finding isomorphisms within each color class, then combining those using the edges between color classes. Zemlyachenko's trick could then be used to individualize $\tilde{O}(\sqrt{n})$ vertices, so that the resulting graph had bounded color classes (which led to the previous-best algorithm for GI).

Babai's recent algorithm does another kind of divide-and-conquer that is sort of along the lines you mention. It either finds a partition of the graph into small parts (where "small" here means some constant fraction smaller than the original graph; the result is that such recursion can only happen $O(\log n)$ times) or finds a large embedded Johnson scheme. In the latter case, it handles the Johnson scheme by a different recursive technique, but then handles the vertices that aren't in the Johnson scheme essentially along the lines you suggest. (Indeed, if you look at the table of contents of Babai's paper you will see there is quite a lot of talk about "local to global" principles, though it's not really the same "local to global" you're talking about here.)


---

### Answer by username_4 on 2016-02-12. Score: 4

NAUTY "colors" nodes with constant depth neighborhood canonical forms. Babai's new algo does likewise with log size neighborhoods.

The kicker is that in a random graph the diameter is about log n, so you end up gobbling the whole thing.

Definitely worth doing for sparse graphs, can really cut down the state space you need to search. Also when you have to go brute force, only check repeated prime cycles, not all k! <https://oeis.org/A186202>

> **Comments:**
> **username_0**: Thanks for your response. I think I need to specify my question more, make it more precise, case based. I am trying to construct an algorithm(I have draft, in case you are interested) and to find similarities with existing algorithm. If I am not wrong, NAUTY not does not "Split"(informally saying) graph the way I have asked,  
> **username_4**: There are a number of options you can pass for the vertex "coloring" phase. I think the default is vertex degree (depth 1 neighborhoods). That is what most splitting algorithms boil down to. A local subgraph around a vertex you can use as a certificate.  
> **username_0**: "I think the default is vertex degree (depth 1 neighborhoods)" --probably this means  1 Dimensional  Weisfeiler-lehman method, in that case $K$  Dimensional  Weisfeiler-lehman((depth $K$  neighborhoods) is not what I meant for sure.  if $K=1$, then it can not handle  regular graph. You can "construct" graph that makes $K$  Dimensional  Weisfeiler-lehman ineffective, for example Cai-Furer-Immerman pair. Certainly  I do not mean that.Note that Nauty uses  1 Dimensional  Weisfeiler-lehman method.  
> **username_4**: Yes, as part of the certificate you can color vertices with linear algebraic properties of their neighborhoods. Sometimes these break symmetries. If you come up with a vertex invariant you find useful for a class of graphs see section 10 on how to add it to NAUTY, http://pallini.di.uniroma1.it/nug25.pdf  

---

