Re: On CFL equivalence and graph isomorphism

miyazaki@symbolix.cs.uoregon.edu (Takunari Miyazaki)
27 Apr 2000 10:47:33 -0400

          From comp.compilers
Related articles
On CFL equivalence and graph isomorphism johnston.p@worldnet.att.net (Paul Johnston) (2000-04-20)
Re: On CFL equivalence and graph isomorphism lex@cc.gatech.edu (2000-04-25)
Re: On CFL equivalence and graph isomorphism colohan+@cs.cmu.edu (Christopher Brian Colohan) (2000-04-25)
Re: On CFL equivalence and graph isomorphism pmoisset@altavista.net (Pablo) (2000-04-25)
Re: On CFL equivalence and graph isomorphism ger@informatik.uni-bremen.de (George Russell) (2000-04-26)
Re: On CFL equivalence and graph isomorphism bdm@cs.anu.edu.au (2000-04-26)
Re: On CFL equivalence and graph isomorphism dmolnar@fas.harvard.edu (David A Molnar) (2000-04-27)
Re: On CFL equivalence and graph isomorphism miyazaki@symbolix.cs.uoregon.edu (2000-04-27)
| List of all articles for this month |
From: miyazaki@symbolix.cs.uoregon.edu (Takunari Miyazaki)
Newsgroups: comp.theory,comp.compilers
Followup-To: comp.theory,comp.compilers
Date: 27 Apr 2000 10:47:33 -0400
Organization: University of Oregon Computer Science Department
Distribution: inet
References: 00-04-140 00-04-167 00-04-184
Keywords: theory

Brendan McKay (bdm@cs.anu.edu.au) wrote:


: Graph isomorphism is not known to be NP-complete, nor to be in P. It
: might turn out to be neither.


As Professor McKay said, the graph-isomorphism problem is not known to
be in P nor NP-complete.


Certain complexity-theoretic evidence suggests that it is unlikely to
be NP-complete (see, e.g., J. Koebler, U. Schoening, and J. Toran, The
graph isomorphism problem: its structural complexity, Birkhaeuser,
1993).


On the other hand, if the vertex degrees are bounded by a constant,
Luks's group-theoretic algorithm performs isomorphism testing in
polynomial time (see E. M. Luks, Isomorphism of graphs of bounded
valence can be tested in polynomial time, J. Comput. System Sci. 25
(1982), 42-65).


Similar group-theoretic methods also yield the
asymptotically-best-known algorithm for general isomorphism testing,
with exp(sqrt(cn log n)) time for n-vertex graphs, due to Babai,
Kantor, Luks, and Zemlyachenko.


Takunari Miyazaki

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.