News for hackers. Stuff that matters.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by harperlee on Wednesday November 04, 2015 @10:23AM (#10507162)
Could anyone provide a good pointer to an introduction more amenable than e.g. Wikipedia? A brief googling provides a lot of material, but I could use a little curation... and that's the sort of thing that sometimes HN is best for. Thanks!
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by Someone on Wednesday November 04, 2015 @11:01AM (#10507454)
What part do you have problems with? Graph isomorphism or quasi-polynomial?

For the first, I would expect https://en.m.wikipedia.org/wiki/Graph_isomorphism (different from https://en.m.wikipedia.org/wiki/Graph_isomorphism_problem) is simple enough for laymen, as long as they know what a graph is.

For the second, I would think https://en.m.wikipedia.org/wiki/Quasi-polynomial_time#Quasi-... could give just enough rope to climb out of the pit you are in.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by JD557 on Wednesday November 04, 2015 @10:55AM (#10507405)
Disclaimer: I don't know much about the subject, but I'll try to help.

Two graphs are isomorphic if they are "the same" graph, as in, if you renamed the edges, the graph would be the same.

For example, if you have the graphs:

G1: A -> B <-> C G1: C -> B <-> A

The only difference between those graphs is the name of the vertices. If you rename them, you get exactly the same graph back.

The first example from the wikipedia page seems like a nice one: https://en.wikipedia.org/wiki/Graph_isomorphism

While the two graphs look different, they are exactly the same.

Quasi-polynomial algorithms, as the name implies, are algorithms that are "almost-polynomial" (ie. slower than polynomial, but faster than exponential). According to https://en.wikipedia.org/wiki/Time_complexity#Quasi-polynomi..., the worst case for a quasi-polynomial algorithm is 2^O(log (n)^c).

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by tinco on Thursday November 05, 2015 @07:13AM (#10512880)
From the example it looks as if this can be solved linearly, because the structures obviously match. To intuit that the algorithm must be exponential, imagine the vertices to be balls on wire. You grab one ball pull it up as the root from which you start to compare. Now it is obvious you have to pick a vertex from the other graph as well to be the root nice from which to begin the comparison, if you pick the wrong one the graphs won't match. So you will have to pick every ball and see if its structure matches. For a tree (a graph without cycles) it's plain to see it's exponential: in the worst case you have to pick each vertex from one graph and then compare its children with the other graph, that's N * N operations. When the graph does have cycles, the problem becomes more complex. How much more complex is what this scientist perhaps put a new upper limit on.