<p>We don't know of any which are provably difficult (if they were provably difficult, then $GI \not\in P$ and therefore $P \neq NP$).  The only study I know of is "The complexity of McKay’s canonical labeling algorithm." by T. Miyazaki who found a way of making the program nauty take exponential time on a certain class of graphs.  When digging up that reference, however, I found that subsequent work has been done on that exact class of graphs - <a href="http://gregtener.com/nishe/">http://gregtener.com/nishe/</a> - and so perhaps that class should no longer be considered hard?</p>

<p>Any links to other results would be much appreciated.</p>

CC BY-SA 3.0
2011-04-09T08:28:53.667Z
Thanks, @Peter. Pity that Greg Tener did not put into his archive any sample Miyazaki graphs.
trg787
CC BY-SA 3.0
2011-04-09T08:36:27.307Z
PS I'm more interested in to see NON-isomorphic graphs which non-isomorphiness is very hard for detecting.
trg787
CC BY-SA 3.0
2011-04-09T10:12:30.930Z
Pascal Schweitzer's PhD thesis contains some constructions of/references to graphs that are assumed to be hard. http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf
5501
CC BY-SA 3.0
2011-04-10T02:25:14.347Z
@trg787 if that's the case, maybe you should edit the question accordingly.
Suresh Venkat
CC BY-SA 3.0
2011-04-10T02:55:22.640Z
@Suresh; Sorry, Suresh, I'm not quite sure I understand what do you mean by "the case"...
trg787
CC BY-SA 3.0
2011-04-10T03:14:03.510Z
"the case" being "more interested in NON-isomorphic graphs for which non-isomorphism is hard"
Suresh Venkat
CC BY-SA 3.0
2011-04-10T05:37:36.993Z
My "more" != "only"
trg787
CC BY-SA 3.0
2011-04-09T04:05:29.200Z
2011-04-09T04:05:29.200Z
Peter Boothe
<p>For the pair 35 I found:<br>
1:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
2:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
3:1,2,3,4,21,22,23,24<br>
4:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
5:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
6:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
7:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
8:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
9:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
10:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
11:1,2,3,4,21,22,23,24<br>
12:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
13:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
14:1,2,3,4,21,22,23,24<br>
15:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
16:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
17:1,2,3,4,21,22,23,24<br>
18:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
19:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
20:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
21:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
22:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
23:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
24:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
25:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
26:1,2,3,4,21,22,23,24<br>
27:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
28:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
29:1,2,3,4,21,22,23,24<br>
30:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
31:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
32:1,2,3,4,21,22,23,24<br>
33:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
34:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
35:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
36:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
37:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40<br>
38:1,2,3,4,21,22,23,24<br>
39:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
40:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39<br>
<br>
I have not yet finished writing the script to verify the results.</p>

CC BY-SA 3.0
2017-03-04T17:12:09.667Z
2017-03-05T10:31:57.020Z
2017-03-05T10:31:57.020Z
Mohamed Mimouni
<blockquote>
  <p>Is the case of strongly regular graphs
  the hardest one for GI testing?</p>
</blockquote>

<p>where "hardest" is used in some "common sense" meaning, or "in average", so to speak.<br>
Wolfram MathWorld mentions some "pathologically hard graphs". What are they?  </p>

<p>My sample set of 25 pairs of graphs: <a href="http://funkybee.narod.ru/graphs.htm" rel="noreferrer">http://funkybee.narod.ru/graphs.htm</a> I tested a lot of others but all of the same kind - SRG or RG from <a href="http://www.maths.gla.ac.uk/~es/srgraphs.html" rel="noreferrer">http://www.maths.gla.ac.uk/~es/srgraphs.html</a> or of genreg.exe. If I generate, say, 1000 graphs then I test all 1000 * (1000 - 1) / 2 pairs. Of course, I don't test obvious ("silly") cases, e.g., graphs with different sorted vectors of degrees etc. But the process is seemed endless and to some extent smells futile. What testing strategy should I choose? Or is this question almost equal to GI problem itself?</p>

<p>I even re-drew on paper a graph from <strong>thesis_pascal_schweitzer.pdf</strong><br>
(suggested by @5501). Its nice pic: <a href="http://funkybee.narod.ru/misc/furer.jpg" rel="noreferrer">http://funkybee.narod.ru/misc/furer.jpg</a><br>
I'm not sure but seems exactly this kind of graphs "which the k-dimensional<br>
Weisfeiler-Lehman algorithm cannot distinguish."<br>
But, gentlemen, to copy graphs to paper from e-books it's too much even for me.  </p>

<pre>
25

0100000000000000000000000
1010000000000000000000000
0101000000000000000000100
0010100000000010000000000
0001010000001000000000000
0000101000000000000000000
0000010100000000000000000
0000001010000000000000000
0000000101000000000000000
0000000010100000000000000
0000000001010000000000000
0000000000101000000000100
0000100000010000000000010
0000000000000010000001010
0001000000000101000000000
0000000000000010100000000
0000000000000001010000000
0000000000000000101000000
0000000000000000010100000
0000000000000000001010000
0000000000000000000101000
0000000000000100000010100
0010000000010000000001000
0000000000001100000000001
0000000000000000000000010

0100000000000000000000000
1010000000000000000000000
0101000000000000000000100
0010100000000010000000000
0001000000001000000010000
0000001000000000000001000
0000010100000000000000000
0000001010000000000000000
0000000101000000000000000
0000000010100000000000000
0000000001010000000000000
0000000000101000000000100
0000100000010000000000010
0000000000000010000001010
0001000000000101000000000
0000000000000010100000000
0000000000000001010000000
0000000000000000101000000
0000000000000000010100000
0000000000000000001010000
0000100000000000000100000
0000010000000100000000100
0010000000010000000001000
0000000000001100000000001
0000000000000000000000010
</pre>

<p><strong>Bounty asking:</strong><br>
<strong>===========</strong><br>
<strong>Could anybody confirm that the 2 last pairs (#34 and #35 in left textarea: <a href="http://funkybee.narod.ru/graphs.htm" rel="noreferrer">http://funkybee.narod.ru/graphs.htm</a> ) are isomorphic?</strong><br>
The matter is that they are based on this: <a href="http://funkybee.narod.ru/misc/mfgraph2.jpg" rel="noreferrer">http://funkybee.narod.ru/misc/mfgraph2.jpg</a> from <strong>A Counterexample in Graph Isomorphism Testing</strong> (1987) by M. Furer but I couldn't get them NON-isomorphic..  </p>

<p><strong>PS#1</strong><br>
I took 4 (must be even square of some positive number (m^2)) fundamental pieces, dovetailed them in a row, -- so I got the 1st global graph, in its copy I swaped (crisscrossing) 2 central edges in each of 4 pieces - so I got the 2nd global graph. But they are turned to be isomorphic. What did I miss or misunderstand in Furer's fairytale?  </p>

<p><strong>PS#2</strong><br>
Seems I got it.<br>
3 pairs #33, #34 and #35 ( the very last 3 pairs on <a href="http://funkybee.narod.ru/graphs.htm" rel="noreferrer">http://funkybee.narod.ru/graphs.htm</a> ) are really amazing cases.  </p>

<pre>
Pair #34:
        G1 and G2 are non-isomorphic graphs.
        In G1: edges (1-3),(2-4). In G2: edges (1-4),(2-3).
        No more diffs in them.

Pair #35:
        G11 and G22 are isomorphic graphs.
        G11 = G1 and G22 is a copy of G2, with only one difference:
        Edges (21-23),(22-24) were swapped like this: (21-24),(22-23)
        ... and two graphs get isomorphic
        as if 2 swaps annihilate each other.
        Odd number of such swaps make the graphs again NON-isomorphic
</pre>  

<p>Graph #33 (20 vertices, 26 edges) is still this: <a href="http://funkybee.narod.ru/misc/mfgraph2.jpg" rel="noreferrer">http://funkybee.narod.ru/misc/mfgraph2.jpg</a><br>
Graphs from ##34, 35 were made just by coupling 2 basic graphs (#33) -- each getting 40 vertices and 60 = 26 + 26 + 8 edges. By 8 new edges I connect 2 "halves" of that new ("big") graph. Really amazing and exactly as Martin Furer says...  </p>

<pre>
Case #33: g = h            ("h" is "g with one possible edges swap in its middle"
                                                  (see the picture))

Case #34: g + g != g + h        (!!!)


Case #35: g + g = h + h         (!!!)
</pre>

CC BY-SA 3.0
2011-04-08T23:41:10.673Z
[Wolfram MathWorld](http://mathworld.wolfram.com/IsomorphicGraphs.html). You really need a lot more than strongly regular graphs to make graph isomorphism testing hard, so the answer is "no". But I'd also like to see a good answer to this question; in particular, how does one construct or find "pathologically hard graphs".
Peter Shor 
CC BY-SA 3.0
2011-04-13T07:25:02.717Z
It is not appropriate to keep editing the question as a log of progress. If you're continuing to work on this, you should take the question offline and post a new one when you have a clear question to ask.
Suresh Venkat
CC BY-SA 3.0
2011-04-13T12:56:53.343Z
You know, @Suresh, right now I downloaded 41MB of SRG (36-15-6-6). And I tested against my algorithm the 6000 first of these graphs. Means I tested 18,000,000 pairs. All was Ok: no isomorphics among them. But it says nothing, either to me or anyone else. What I need is a counterexample.
trg787
CC BY-SA 3.0
2011-04-13T15:45:58.373Z
this is not the right forum for that. Questions of the form "are these two specific graphs isomorphic or not" are not the right kinds of questions for this site. More general questions are.
Suresh Venkat
CC BY-SA 3.0
2014-09-16T16:58:28.067Z
![enter image description here](https://i.sstatic.net/UZtJv.jpg) I tried with APSP matrix.... isomorphism was detected. in graph no 33 (20 vertices) These are images, http://postimg.org/image/o8v892koz/05f762ec/ APSP matrices were rearranged to each other , so graph pairs are isomorphic. ** previously , I miscalculated. http://postimg.org/image/6nzlmfe9v/ Trying others!
Michael
CC BY-SA 3.0
2017-03-04T14:21:46.690Z
If I find solutions for each pair, is that I can publish them on my web page?
Mohamed Mimouni
<ds.algorithms><graph-isomorphism>
Hard Instances for graph isomorphism testing
trg787
# Hard Instances for graph isomorphism testing

(Asked by: username_0 on 2011-04-08)

Is the case of strongly regular graphs
  the hardest one for GI testing?

where "hardest" is used in some "common sense" meaning, or "in average", so to speak.
Wolfram MathWorld mentions some "pathologically hard graphs". What are they?  
My sample set of 25 pairs of graphs: http://funkybee.narod.ru/graphs.htm I tested a lot of others but all of the same kind - SRG or RG from http://www.maths.gla.ac.uk/~es/srgraphs.html or of genreg.exe. If I generate, say, 1000 graphs then I test all 1000 * (1000 - 1) / 2 pairs. Of course, I don't test obvious ("silly") cases, e.g., graphs with different sorted vectors of degrees etc. But the process is seemed endless and to some extent smells futile. What testing strategy should I choose? Or is this question almost equal to GI problem itself?
I even re-drew on paper a graph from thesis_pascal_schweitzer.pdf
(suggested by @5501). Its nice pic: http://funkybee.narod.ru/misc/furer.jpg
I'm not sure but seems exactly this kind of graphs "which the k-dimensional
Weisfeiler-Lehman algorithm cannot distinguish."
But, gentlemen, to copy graphs to paper from e-books it's too much even for me.  

25

0100000000000000000000000
1010000000000000000000000
0101000000000000000000100
0010100000000010000000000
0001010000001000000000000
0000101000000000000000000
0000010100000000000000000
0000001010000000000000000
0000000101000000000000000
0000000010100000000000000
0000000001010000000000000
0000000000101000000000100
0000100000010000000000010
0000000000000010000001010
0001000000000101000000000
0000000000000010100000000
0000000000000001010000000
0000000000000000101000000
0000000000000000010100000
0000000000000000001010000
0000000000000000000101000
0000000000000100000010100
0010000000010000000001000
0000000000001100000000001
0000000000000000000000010

0100000000000000000000000
1010000000000000000000000
0101000000000000000000100
0010100000000010000000000
0001000000001000000010000
0000001000000000000001000
0000010100000000000000000
0000001010000000000000000
0000000101000000000000000
0000000010100000000000000
0000000001010000000000000
0000000000101000000000100
0000100000010000000000010
0000000000000010000001010
0001000000000101000000000
0000000000000010100000000
0000000000000001010000000
0000000000000000101000000
0000000000000000010100000
0000000000000000001010000
0000100000000000000100000
0000010000000100000000100
0010000000010000000001000
0000000000001100000000001
0000000000000000000000010

Bounty asking:
===========
Could anybody confirm that the 2 last pairs (#34 and #35 in left textarea: http://funkybee.narod.ru/graphs.htm ) are isomorphic?
The matter is that they are based on this: http://funkybee.narod.ru/misc/mfgraph2.jpg from A Counterexample in Graph Isomorphism Testing (1987) by M. Furer but I couldn't get them NON-isomorphic..  
PS#1
I took 4 (must be even square of some positive number (m^2)) fundamental pieces, dovetailed them in a row, -- so I got the 1st global graph, in its copy I swaped (crisscrossing) 2 central edges in each of 4 pieces - so I got the 2nd global graph. But they are turned to be isomorphic. What did I miss or misunderstand in Furer's fairytale?  
PS#2
Seems I got it.
3 pairs #33, #34 and #35 ( the very last 3 pairs on http://funkybee.narod.ru/graphs.htm ) are really amazing cases.  

Pair #34:
        G1 and G2 are non-isomorphic graphs.
        In G1: edges (1-3),(2-4). In G2: edges (1-4),(2-3).
        No more diffs in them.

Pair #35:
        G11 and G22 are isomorphic graphs.
        G11 = G1 and G22 is a copy of G2, with only one difference:
        Edges (21-23),(22-24) were swapped like this: (21-24),(22-23)
        ... and two graphs get isomorphic
        as if 2 swaps annihilate each other.
        Odd number of such swaps make the graphs again NON-isomorphic

Graph #33 (20 vertices, 26 edges) is still this: http://funkybee.narod.ru/misc/mfgraph2.jpg
Graphs from ##34, 35 were made just by coupling 2 basic graphs (#33) -- each getting 40 vertices and 60 = 26 + 26 + 8 edges. By 8 new edges I connect 2 "halves" of that new ("big") graph. Really amazing and exactly as Martin Furer says...  

Case #33: g = h            ("h" is "g with one possible edges swap in its middle"
                                                  (see the picture))

Case #34: g + g != g + h        (!!!)


Case #35: g + g = h + h         (!!!)

**Tags:** ds.algorithms, graph-isomorphism
> **Comments:**
> **username_1**: [Wolfram MathWorld](http://mathworld.wolfram.com/IsomorphicGraphs.html). You really need a lot more than strongly regular graphs to make graph isomorphism testing hard, so the answer is "no". But I'd also like to see a good answer to this question; in particular, how does one construct or find "pathologically hard graphs".  
> **username_2**: It is not appropriate to keep editing the question as a log of progress. If you're continuing to work on this, you should take the question offline and post a new one when you have a clear question to ask.  
> **username_0**: You know, @Suresh, right now I downloaded 41MB of SRG (36-15-6-6). And I tested against my algorithm the 6000 first of these graphs. Means I tested 18,000,000 pairs. All was Ok: no isomorphics among them. But it says nothing, either to me or anyone else. What I need is a counterexample.  
> **username_2**: this is not the right forum for that. Questions of the form "are these two specific graphs isomorphic or not" are not the right kinds of questions for this site. More general questions are.  
> **username_3**: ![enter image description here](https://i.sstatic.net/UZtJv.jpg) I tried with APSP matrix.... isomorphism was detected. in graph no 33 (20 vertices) These are images, http://postimg.org/image/o8v892koz/05f762ec/ APSP matrices were rearranged to each other , so graph pairs are isomorphic. ** previously , I miscalculated. http://postimg.org/image/6nzlmfe9v/ Trying others!  
> **username_4**: If I find solutions for each pair, is that I can publish them on my web page?  

---

## 2 answers

### Answer by username_5 on 2011-04-09. Score: 17

We don't know of any which are provably difficult (if they were provably difficult, then $GI \not\in P$ and therefore $P \neq NP$). The only study I know of is "The complexity of McKay’s canonical labeling algorithm." by T. Miyazaki who found a way of making the program nauty take exponential time on a certain class of graphs. When digging up that reference, however, I found that subsequent work has been done on that exact class of graphs - <http://gregtener.com/nishe/> - and so perhaps that class should no longer be considered hard?

Any links to other results would be much appreciated.

> **Comments:**
> **username_0**: Thanks, @Peter. Pity that Greg Tener did not put into his archive any sample Miyazaki graphs.  
> **username_0**: PS I'm more interested in to see NON-isomorphic graphs which non-isomorphiness is very hard for detecting.  
> **username_6**: Pascal Schweitzer's PhD thesis contains some constructions of/references to graphs that are assumed to be hard. http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf  
> **username_2**: @trg787 if that's the case, maybe you should edit the question accordingly.  
> **username_0**: @Suresh; Sorry, Suresh, I'm not quite sure I understand what do you mean by "the case"...  
> **username_2**: "the case" being "more interested in NON-isomorphic graphs for which non-isomorphism is hard"  
> **username_0**: My "more" != "only"  

---

### Answer by username_4 on 2017-03-04. Score: 0

For the pair 35 I found:  
1:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
2:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
3:1,2,3,4,21,22,23,24  
4:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
5:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
6:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
7:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
8:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
9:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
10:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
11:1,2,3,4,21,22,23,24  
12:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
13:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
14:1,2,3,4,21,22,23,24  
15:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
16:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
17:1,2,3,4,21,22,23,24  
18:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
19:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
20:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
21:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
22:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
23:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
24:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
25:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
26:1,2,3,4,21,22,23,24  
27:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
28:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
29:1,2,3,4,21,22,23,24  
30:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
31:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
32:1,2,3,4,21,22,23,24  
33:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
34:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
35:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
36:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
37:5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40  
38:1,2,3,4,21,22,23,24  
39:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
40:6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39  
  
I have not yet finished writing the script to verify the results.


---

