16
$\begingroup$

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         (!!!)
Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Wolfram MathWorld. 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". $\endgroup$
    – Peter Shor
    Apr 8, 2011 at 23:41
  • 3
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Apr 13, 2011 at 7:25
  • $\begingroup$ 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. $\endgroup$
    – trg787
    Apr 13, 2011 at 12:56
  • 5
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Apr 13, 2011 at 15:45
  • $\begingroup$ !enter image description here I tried with APSP matrix.... isomorphism was detected. in graph no 33 (20 vertices) These are images, postimg.org/image/o8v892koz/05f762ec APSP matrices were rearranged to each other , so graph pairs are isomorphic. ** previously , I miscalculated. postimg.org/image/6nzlmfe9v Trying others! $\endgroup$
    – Michael
    Sep 16, 2014 at 16:58

2 Answers 2

Reset to default
17
+50
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks, @Peter. Pity that Greg Tener did not put into his archive any sample Miyazaki graphs. $\endgroup$
    – trg787
    Apr 9, 2011 at 8:28
  • $\begingroup$ PS I'm more interested in to see NON-isomorphic graphs which non-isomorphiness is very hard for detecting. $\endgroup$
    – trg787
    Apr 9, 2011 at 8:36
  • 2
    $\begingroup$ Pascal Schweitzer's PhD thesis contains some constructions of/references to graphs that are assumed to be hard. users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf $\endgroup$
    – 5501
    Apr 9, 2011 at 10:12
  • 1
    $\begingroup$ @Suresh; Sorry, Suresh, I'm not quite sure I understand what do you mean by "the case"... $\endgroup$
    – trg787
    Apr 10, 2011 at 2:55
  • 2
    $\begingroup$ "the case" being "more interested in NON-isomorphic graphs for which non-isomorphism is hard" $\endgroup$
    – Suresh Venkat
    Apr 10, 2011 at 3:14
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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