4 ms·

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,

by 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.

by JD557 11y ago

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.