3 ms·

even small graphs can be made to look very different just by moving their nodes around I'm curious: for the graph isomorphism problem, how are the graphs defin

by rsp1984 7y ago

even small graphs can be made to look very different just by moving their nodes around I'm curious: for the graph isomorphism problem, how are the graphs defined then? It seems there must be a geometric component in there because if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same, wouldn't it?

DominikPeters 7y ago
Graphs are given as abstract sets of vertices and sets of edges (as adjacency lists or matrices). The problem is that corresponding vertices in the two graphs may not have the same label, so to solve graph isomorphism naively, one would need to try all n! possible bijections between the vertex sets (where n is the number of vertices).
- sischoel 7y ago
  Wikipedia has a nice picture of two graphs that are isomorph: https://en.wikipedia.org/wiki/Graph_isomorphism https://en.wikipedia.org/wiki/Graph_isomorphism. It should be noted than one of the common used algorithms, called VF2, and descendants of it basically just check all possible bijections, although they use some heuristics to prune the search tree.
  - shawnz 7y ago
    I think pictorial representations are what is confusing the grandparent. The problem isn't about comparing two graphs that look different visually, it's about comparing two graphs which have differently named labels (but might still have the same structure). The graph isomorphism algorithm doesn't know anything about where on the page you drew the nodes, just what is connected to what
- rsp1984 7y ago
  Thanks much for the clarification. I didn't know that one was "allowed" to change labels. It makes sense now.
TuringTest 7y ago
Not if the number of nodes is high, no. The complexity of the naif algorithm grows exponentially, making it unmanageable very fast. In order to show that one node in the first graph correspond to a particular node (i.e. is isomorphic) in the second graph, its not enough to check that they have the same number of outgoing edges. You have then to check all the connected nodes, and then make sure that those are also isomorphic to the respective same nodes in the same roles at the other graph. This makes the problem recursive and dependent on the rest of the graph; you can't simply split the graph and solve each sub-problem fast.
Someone 7y ago
”It seems there must be a geometric component in there” No, there isn’t. ”if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same” No, it isn’t, unless you know a novel argument that hasn’t been thought of yet by mathematicians. It is fairly simple for graphs with very few vertices or very few edges, but in general, it isn’t easy at all.
- sdenton4 7y ago
  You might say that it's easy in general (since all but a handful of isomorphism classes are easily distinguished), but hard in full generality. :)
stephencanon 7y ago
The problem is to show that the graphs are the same or different up to relabeling of the vertices. I.e. the graphs 0-1-2 0-2-1 are the same if you swap the labels 1 and 2. You could try to brute force it by trying all possible permutations of vertex labels, but there are n! of those to try, so that doesn't help much. Any polynomial-ish algorithm would need to do something clever that takes advantage of the structure of the problem.
ggggtez 7y ago
A graph is defined as it always is. A set of edges that connect nodes by their IDs. We can use this arrow notation for convenience. Imagine you have a graph: a->b b->c c->d d->b Is that the same as this graph? a'->b' b'->c' c'->a' d'->a' You can sort the edges alphabetically in the first graph. Then you could take the second graphs labels, and figure out if there is a way to "relabel" it, so when you sort those edges alphabetically, you can the same result. There are |V|! possible ways to relabel |V| vertices. Other algorithms are better than "try everything", but this shows why it's not trivial. Like a puzzle, you can put the pieces into place, and everything looks right, but then when you get to the end you realize one piece doesn't fit. Does that mean it's not-isomorphic? or maybe you just need to re-arrange the pieces differently? That's why the complexity is so high.
vignesh_m 7y ago
Its actually pretty hard for even humans to eyeball a graph and figure it out. For example, the wiki article on the peterson graph (https://en.wikipedia.org/wiki/Petersen_graph https://en.wikipedia.org/wiki/Petersen_graph) has a few drawings that you cant easily say are the same graph.

DominikPeters 7y ago

Graphs are given as abstract sets of vertices and sets of edges (as adjacency lists or matrices). The problem is that corresponding vertices in the two graphs may not have the same label, so to solve graph isomorphism naively, one would need to try all n! possible bijections between the vertex sets (where n is the number of vertices).

sischoel 7y ago
Wikipedia has a nice picture of two graphs that are isomorph: https://en.wikipedia.org/wiki/Graph_isomorphism https://en.wikipedia.org/wiki/Graph_isomorphism. It should be noted than one of the common used algorithms, called VF2, and descendants of it basically just check all possible bijections, although they use some heuristics to prune the search tree.
- shawnz 7y ago
  I think pictorial representations are what is confusing the grandparent. The problem isn't about comparing two graphs that look different visually, it's about comparing two graphs which have differently named labels (but might still have the same structure). The graph isomorphism algorithm doesn't know anything about where on the page you drew the nodes, just what is connected to what
rsp1984 7y ago
Thanks much for the clarification. I didn't know that one was "allowed" to change labels. It makes sense now.

TuringTest 7y ago

Not if the number of nodes is high, no. The complexity of the naif algorithm grows exponentially, making it unmanageable very fast. In order to show that one node in the first graph correspond to a particular node (i.e. is isomorphic) in the second graph, its not enough to check that they have the same number of outgoing edges. You have then to check all the connected nodes, and then make sure that those are also isomorphic to the respective same nodes in the same roles at the other graph. This makes the problem recursive and dependent on the rest of the graph; you can't simply split the graph and solve each sub-problem fast.

Someone 7y ago

”It seems there must be a geometric component in there” No, there isn’t. ”if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same” No, it isn’t, unless you know a novel argument that hasn’t been thought of yet by mathematicians. It is fairly simple for graphs with very few vertices or very few edges, but in general, it isn’t easy at all.

sdenton4 7y ago
You might say that it's easy in general (since all but a handful of isomorphism classes are easily distinguished), but hard in full generality. :)

stephencanon 7y ago

The problem is to show that the graphs are the same or different up to relabeling of the vertices. I.e. the graphs 0-1-2 0-2-1 are the same if you swap the labels 1 and 2. You could try to brute force it by trying all possible permutations of vertex labels, but there are n! of those to try, so that doesn't help much. Any polynomial-ish algorithm would need to do something clever that takes advantage of the structure of the problem.

ggggtez 7y ago

A graph is defined as it always is. A set of edges that connect nodes by their IDs. We can use this arrow notation for convenience. Imagine you have a graph: a->b b->c c->d d->b Is that the same as this graph? a'->b' b'->c' c'->a' d'->a' You can sort the edges alphabetically in the first graph. Then you could take the second graphs labels, and figure out if there is a way to "relabel" it, so when you sort those edges alphabetically, you can the same result. There are |V|! possible ways to relabel |V| vertices. Other algorithms are better than "try everything", but this shows why it's not trivial. Like a puzzle, you can put the pieces into place, and everything looks right, but then when you get to the end you realize one piece doesn't fit. Does that mean it's not-isomorphic? or maybe you just need to re-arrange the pieces differently? That's why the complexity is so high.

vignesh_m 7y ago

Its actually pretty hard for even humans to eyeball a graph and figure it out. For example, the wiki article on the peterson graph (https://en.wikipedia.org/wiki/Petersen_graph https://en.wikipedia.org/wiki/Petersen_graph) has a few drawings that you cant easily say are the same graph.