News for hackers. Stuff that matters.
Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T... by eveningcoffee on Thursday November 12, 2015 @01:06PM (#10554882)
I also hear that some people use graph isomorphism to compare files, do optical character recognition, and analyze social networks, but it seems highly probable to me that GI is not the central workhorse (or even a main workhorse) in these fields.

Can somebody in HN more familiar with this add a comment about this?

Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T... by CJefferson on Thursday November 12, 2015 @04:26PM (#10556259)
Graph Isomorphism is indeed not used much in these field. Subgraph isomorphism (and variants of it) are very useful, and surprisingly (well, suprising to me), the techniques for solving graph isomorphism and subgraph isomorphism are entirely different.

On practical use of graph isomorphism is finding symmetries in programs -- (basically) build an AST, and then run graph isomorphism on that.

Also, the algorithms used for graph isomorphism are used (with modification) to solve a large range of group theory problems, including group intersection, so this might help with a large range of other group theory problems.

Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T... by jules on Thursday November 12, 2015 @01:13PM (#10554943)
Maybe there is somebody who uses GI to do those things, but that is not a standard method and likely a bad idea. For comparing files the standard method is just a diff based on Levenshtein distance, and the standard methods for character recognition are various forms of machine learning (e.g. SVM, NN).
Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T... by OJFord on Thursday November 12, 2015 @04:24PM (#10556241)
Social networks sounds like a likely application though.

Consider "Graph A is Alice's network of friends; B is Bob's. Do they know exactly and only the same people?"

That might be slightly contrived. But it could be used to indicate how introverted a certain community is!

Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T... by bmm6o on Thursday November 12, 2015 @04:38PM (#10556335)
In your hypothetical case the vertices would be labeled by friends' names or ids. So you only have to check whether the obvious isomorphism applies i.e. that the graphs are equivalent as sets.
Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T... by OJFord on Thursday November 12, 2015 @09:32PM (#10557679)
Ah, yes that's true of course - I clearly wasn't thinking..

Well, then I can't even contrive an example! Still, it's interesting; I wish I had the background to understand it better.