6 ms·

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

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!

JD557 11y ago
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 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-polynomial_time https://en.wikipedia.org/wiki/Time_complexity#Quasi-polynomi..., the worst case for a quasi-polynomial algorithm is 2^O(log (n)^c).
- tinco 11y ago
  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.
Someone 11y ago
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 https://en.m.wikipedia.org/wiki/Graph_isomorphism (different from https://en.m.wikipedia.org/wiki/Graph_isomorphism_problem 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-polynomial_time https://en.m.wikipedia.org/wiki/Quasi-polynomial_time#Quasi-... could give just enough rope to climb out of the pit you are in.

JD557 11y ago

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 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-polynomial_time https://en.wikipedia.org/wiki/Time_complexity#Quasi-polynomi..., the worst case for a quasi-polynomial algorithm is 2^O(log (n)^c).

tinco 11y ago
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.

Someone 11y ago

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 https://en.m.wikipedia.org/wiki/Graph_isomorphism (different from https://en.m.wikipedia.org/wiki/Graph_isomorphism_problem 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-polynomial_time https://en.m.wikipedia.org/wiki/Quasi-polynomial_time#Quasi-... could give just enough rope to climb out of the pit you are in.