6
$\begingroup$

(1) Which graph classes are extremely tough to test for graph non-isomorphic pairs from isomorphic pairs?

(2) Is there a repository of adjacencies from such classes?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
6
$\begingroup$

There is a move towards creating a "standard" benchmark set for graph isomorphism, but it didn't happen yet. Meanwhile, the largest collection that includes hard graphs as well as easy graphs is here. To make examples of difficult nonisomorphic pairs, take two graphs with the same parameters and randomly label them. For difficult isomorphic pairs take two random labellings of the same graph.

The graphs here that will cause trouble to most programs are in the classes ag, cfi, had, latin-sw, pg, pp, f-lex.

Improve this answer
$\endgroup$
5
$\begingroup$

In ScrewBox: a Randomized Certifying Graph-Non-Isomorphism Algorithm by Kutz and Schweitzer it is stated that "It is generally accepted that the incidence graphs of finite projective planes confront graph isomorphism algorithms with great challenges."

Also the PhD Thesis of Schweitzer discusses difficult graphs (including incidence graph of projective planes) in section 2.8.

I do not know any repository of adjacencies of these graph, but Moorhouse has data online for known projective planes of order 27 online. Also the paper of Kutz and Schweitzer as well as the thesis of Schweitzer both cite data that Royle has on projective planes on order 16 but that link seems to broken for me right now.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I saw that thesis too I dont see why he considers these difficult $\endgroup$
    – Turbo
    Commented Dec 20, 2015 at 3:09
  • $\begingroup$ In the intro of the first article I link the authors say that the projective planes among the hardest know instance for nauty. I believe they are using nauty as a benchmark as to what is hard or not. $\endgroup$
    – John Machacek
    Commented Dec 20, 2015 at 3:12
  • $\begingroup$ JohnMachacek is there a list of adjacencies from proj plane? $\endgroup$
    – Turbo
    Commented Dec 20, 2015 at 3:20
  • $\begingroup$ In the data link above there are text files which are basically adjacency lists for the incidence graph of each projective plane. $\endgroup$
    – John Machacek
    Commented Dec 20, 2015 at 3:34
  • $\begingroup$ Can you give example of one link? link I click downloads unknown file formats. $\endgroup$
    – Turbo
    Commented Dec 20, 2015 at 3:47
5
$\begingroup$

Paper: A large database of graphs and its use for benchmarking graph isomorphism algorithms

The graph instances and graph generator software are here:

http://mivia.unisa.it/datasets/graph-database/arg-database/

Improve this answer
$\endgroup$
5
  • $\begingroup$ do we get adjacencies of graph pairs that can be fed to MATLAB? $\endgroup$
    – Turbo
    Commented Dec 20, 2015 at 7:55
  • $\begingroup$ @Turbo The adjacencies are in the DOWNLOAD section, e.g: mivia.unisa.it/database/graphsdb.zip I think you will need to modify their program to export them to Matlab, check the .pdf with example usage. $\endgroup$
    – joro
    Commented Dec 20, 2015 at 8:19
  • $\begingroup$ I looked and I also looked at their format it is a bit unclear $\endgroup$
    – Turbo
    Commented Dec 20, 2015 at 8:21
  • $\begingroup$ also what is unclear is they have hard graph iso instances but do not have graph non-iso instances .. so how does it work? $\endgroup$
    – Turbo
    Commented Dec 20, 2015 at 8:22
  • $\begingroup$ @Turbo I think you will need their library described in the pdf and then export to your needs. $\endgroup$
    – joro
    Commented Dec 20, 2015 at 8:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .