Graph isomorphism

1. Graph Isomorphism
Algorithms and networks

2. Graph Isomorphism 2
Today
•Graph isomorphism: definition
•Complexity: isomorphism completeness
•The refinement heuristic
•Isomorphism for trees
–Rooted trees
–Unrooted trees

3. Graph Isomorphism 3
Graph Isomorphism
•Two graphs G=(V,E) and H=(W,F) are
isomorphicif there is a bijective function f:
V W such that for all v, wV:
–{v,w} E {f(v),f(w)} F

4. Graph Isomorphism 4
Variant for labeled graphs
•Let G = (V,E), H=(W,F) be graphs with vertex
labelings l: V L, l’L.
•G and H are isomorphic labeled graphs, if there is
a bijective function f: V W such that
–For all v, wV: {v,w} E {f(v),f(w)} F
–For all vV: l(v) = l’(f(v)).
•Application: organic chemistry:
–determining if two molecules are identical.

5. Graph Isomorphism 5
Complexity of graph
isomorphism
•Problem is in NP, but
–No NP-completeness proof is known
–No polynomial time algorithm is known
NP
NP-complete
P
Graph
isomorphism
If P NP
?

6. Graph Isomorphism 6
Isomorphism-complete
•Problems are isomorphism-
complete, if they are `equally hard’
as graph isomorphism
–Isomorphism of bipartite graphs
–Isomorphism of labeled graphs
–Automorphismof graphs
•Given: a graph G=(V,E)
•Question: is there a non-trivial
automorphism, i.e., a bijective function f:
V V, not the identity, with for all
v,wV:
–{v,w} E, if and only if {f(v),f(w)} E.

7. Graph Isomorphism 7
More isomorphism complete
problems
•Finding a graph isomorphism f
•Isomorphism of semi-groups
•Isomorphism of finite automata
•Isomorphism of finite algebra’s
•Isomorphism of
–Connected graphs
–Directed graphs
–Regular graphs
–Perfect graphs
–Chordal graphs
–Graphs that are isomorphic with their complement

8. Graph Isomorphism 8
Special cases are easier
•Polynomial time algorithms for
–Graphs of bounded degree
–Planar graphs
–Trees
•Expected polynomial time for random
graphs
This course

9. Graph Isomorphism 9
An equivalence relation on
vertices
•Say v ~ w, if and only if there is an
automorphism mapping vto w.
•~ is an equivalence relation
•Partitions the vertices in automorphism
classes
•Tells on structure of graph

10. Graph Isomorphism 10
Iterative vertex partition heuristic
the idea
•Partition the vertices of G and H in classes
•Each class for G has a corresponding class
for H.
•Property: vertices in class must be mapped
to vertices in corresponding class
•Refine classes as long as possible
•When no refinement possible, check all
possible ways that `remain’.

11. Graph Isomorphism 11
Iterative vertex partition heuristic
•If |V| |W|, or |E| |F|, output: no. Done.
•Otherwise, we partition the vertices of G and H
into classes, such that
–Each class for G has a corresponding class for H
–If f is an isomorphism from G to H, then f(v) belongs to
the class, corresponding to the class of v.
•First try: vertices belong to the same class, when
they have the same degree.
–If f is an isomorphism, then the degree of f(v) equals
the degree of vfor each vertex v.

12. Graph Isomorphism 12
Scheme
•Start with sequence SG = (A
1) of subsets of G
with A
1=V, and sequence SH = (B
1) of subsets of
H with B
1=W.
•Repeat until …
–Replace A
iin SG by A
i1,…,A
irand replace B
iin SH by
B
i1,…,B
ir.
•A
i1,…,A
iris partition of A
i
•B
i1,…,B
iris partition of B
i
•For each isormorphism f: vin A
ijif and only if f(v) in B
ij

13. Graph Isomorphism 13
Possible refinement
•Count for each vertex in A
iand B
ihow many
neighbors they have in A
jand B
jfor some i, j.
•Set A
is= {vin A
i| vhas sneighbors in A
j}.
•Set B
is= {vin B
i| vhas sneighbors in B
j}.
•Invariant: for all vin the ith set in SG, f(v) in the
ith set in SH.
•If some |A
i| |B
i|, then stop: no isomorphism.

14. Graph Isomorphism 14
Other refinements
•Partition upon other characteristics of
vertices
–Label
–Number of vertices at distance d(in a set A
i).
–…

15. Graph Isomorphism 15
After refining
•If each A
icontains one vertex: check the
only possible isomorphism.
•Otherwise, cleverly enumerate all functions
that are still possible, and check these.
•Works well in practice!

16. Graph Isomorphism 16
Isomorphism on trees
•Linear time algorithm to test if two
(labeled) trees are isomorphic.
•Algorithm to test if two rootedtreesare
isomorphic.
•Used as a subroutine for unrooted trees.

17. Graph Isomorphism 17
Rooted tree isomorphism
•For a vertex vin T, let T(v) be the subtree of
T with vas root.
•Levelof vertex: distance to root.
•If T
1
and T
2
have different number of levels:
not isomorphic, and we stop. Otherwise, we
continue:

18. Graph Isomorphism 18
Structure of algorithm
•Tree is processed level by level, from bottom to
root
•Processing a level:
–A long labelfor each vertex is computed
–This is transformed to a short label
•Vertices in the same layer whose subtrees are
isomorphic get the same labels:
–If vand won the same level, then
•L(v)=L(w), if and only if T(v) and T(w) are
isomorphic with an isomorphism that maps vto w.

19. Graph Isomorphism 19
Labeling procedure
•For each vertex, get the set of labels assigned to its
children.
•Sort these sets.
–Bucketsort the pairs (L(w), v) for T
1
, w child of v
–Bucketsort the pairs (L(w), v) for T
2
, w child of v
•For each v, we now have a long labelLL(v) which
is the sorted set of labels of the children.
•Use bucketsort to sort the vertices in T
1
and T
2
such that vertices with same long label are
consecutive in ordering.

20. Graph Isomorphism 20
On sorting w.r.t. the long lists (1)
•Preliminary work:
–Sort the nodes is the layer on the number of
children they have.
•Linear time. (Counting sort / Radix sort.)
–Make a set of pairs (j,i) with (j,i) in the set
when the jth number in a long list is i.
–Radix sort this set of pairs.

21. Graph Isomorphism 21
On sorting w.r.t. the long lists (2)
•Let qbe the maximum length of a long list
•Repeat
–Distribute among buckets the nodes with at least q
children, with respect to the qth label in their long list
•Nodes distributed in buckets in earlier round are taken here in
the order as they appear in these buckets.
•The sorted list of pairs (j,i) is used to skip empty buckets in this
step.
–q--;
–Until q=0.

22. Graph Isomorphism 22
After vertices are sorted with
respect to long label
•Give vertices with same long label same
short label (start counting at 0), and repeat
at next level.
•If we see that the set of labels for a level of
T
1
is not equal to the set for the same level
of T
2
, stop: not isomorphic.

23. Graph Isomorphism 23
Time
•One layer with n
1nodes with n
2nodes in
next layer costs O(n
1+ n
2) time.
•Total time: O(n).

24. Graph Isomorphism 24
Unrooted trees
•Centerof a tree
–A vertex v with the property that the maximum distance
to any other vertex in T is as small as possible.
–Each tree has a center of one or two vertices.
•Finding the center:
–Repeat until we have a vertex or a single edge:
•Remove all leaves from T.
–O(n) time: each vertex maintains current degree in
variable. Variables are updated when vertices are
removed, and vertices put in set of leaves when their
degree becomes 1.

25. Graph Isomorphism 25
Isomorphism of unrooted trees
•Note: the center must be mapped to the center
•If T
1
and T
2
both have a center of size 1:
–Use those vertices as root.
•If T
1
and T
2
both have a center of size 2:
–Try the two different ways of mapping the centers
–Or: subdivide the edge between the two centers and
take the new vertices as root
•Otherwise: not isomorphic.
•1 or 2 calls to isomorphism of rooted trees: O(n).

26. Graph Isomorphism 26
Conclusions
•Similar methods work for finding
automorphisms
•We saw: heuristic for arbitrary graphs,
algorithm for trees
•There are algorithms for several special
graph classes (e.g., planar graphs, graphs of
bounded degree,…)