Newsgroups: sci.math
From: Hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 1997/09/29
Subject: Re: Graph Theory Enumeration

jhni...@luz.ve (Jose H. Nieto) writes:

[ Much good stuff about enumerating graphs.  On graph isomorphism: ]

> Of course an algorithm does exist! Given two graphs with n vertices
> (graphs with different number of vertices aren't isomorphic) check
> each bijection between the sets of vertices to see if the adjacency
> relationship is preserved. The problem is that there are n! bijections,
> so this "brute force" algorithm is impractical except for small n. No
> EFFICIENT (i.e. with polinomially bounded execution time) algorithm is
> known, and probably it does not exist. A related problem, the SUBGRAPH
> ISOMORPHISM problem (i.e. to determine if a graph G contains a subgraph
> isomorphic to another given graph H) is known to be NP-complete, so we

> are talking of computationally complex problems indeed.
Which is generally correct, except that you mustn't use the
NP-complete problem SUBGRAPH ISOMORPHISM (S.I.) to argue that GRAPH
ISOMORPHISM (G.I.) is difficult.  Isomorphism is not what makes S.I.
hard--the subgraph to test is can be an empty graph or a clique, for
which G.I. is trivial.  It's selecting a subset of vertices to induce
the subgraph that makes S.I. NP-complete.  So calling these problems
"related" is misleading.

Not that anyone has gotten anywhere near a polynomial-time algorithm
for G.I., but neither is anyone near proving it NP-hard (unless
something has been accomplished in the last 15 years, which I'd like
to hear about).

Dan Hoey                                e-mailed and (hopefully) posted
Hoey@AIC.NRL.Navy.Mil