5
$\begingroup$

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 is the closest I got to mine, but it does not answer my query.

$\endgroup$
  • 1
    $\begingroup$ If the construction of a canonical labeling falls into your question, then algorithms for bounded width (tree-width ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6979003 or rank-width ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7354440) or others based on graph decompositions (see the book by Martin Grohe) are such examples. $\endgroup$ – M. kanté Feb 8 '16 at 8:51
  • $\begingroup$ 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... $\endgroup$ – vzn Feb 8 '16 at 16:15
  • $\begingroup$ another direction is the 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. $\endgroup$ – vzn Feb 8 '16 at 16:19
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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, $\endgroup$ – Jim Feb 12 '16 at 22:19
  • 3
    $\begingroup$ 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. $\endgroup$ – Chad Brewbaker Feb 12 '16 at 23:07
  • $\begingroup$ "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. $\endgroup$ – Jim Feb 12 '16 at 23:31
  • 2
    $\begingroup$ 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, pallini.di.uniroma1.it/nug25.pdf $\endgroup$ – Chad Brewbaker Feb 13 '16 at 14:15

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.