From: Douglas W Bass Subject: Re: Graph theorists - do you know an algorithm to detect Isomorphic graphs? Date: 30 Jun 1999 05:07:38 GMT Newsgroups: sci.math Keywords: complexity of graph-isomorphism problem Stuart Anderson wrote: : Is there an algorithm known to graph theorists which establishes : isomorphism? If so can anyone supply a refence to it? I haven't thought about it lately, but I believe graph isomorphism is NP-complete. Cormen, Leiserson and Rivest asks readers to show it is in NP as an exercise. Best wishes, Douglas Bass ------------------------------------------------------------------------- Douglas Bass Ph.D Student, Computer Science, University of Texas at Dallas Phone: (972)-883-6444 email: dbass@utdallas.edu URL: http://www.utdallas.edu/~dbass The opinions expressed are strictly my own, and are not necessarily those of the faculty or administration of the University of Texas at Dallas. ============================================================================== From: alexandershtannikov@my-deja.com Subject: Re: Graph theorists - do you know an algorithm to detect Isomorphic graphs? Date: Wed, 30 Jun 1999 09:53:24 GMT Newsgroups: sci.math > Stuart Anderson wrote: > > I haven't thought about it lately, but I believe graph isomorphism is > NP-complete. Cormen, Leiserson and Rivest asks readers to show it is in > NP as an exercise. > It is not proved that this task is NP-complete. For this task defined own complexity class named gamma-NP. Obviously this class belongs to NP. So, an exponential algorithm for this task exists. But also there are many polynomial algorithm without proof of correctness. e.g. we can compare the characteristic polynomials of the matrices of two graphs. Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't. ============================================================================== From: gwoegi@fmatbds01.tu-graz.ac.REMOVE.at (Gerhard J. Woeginger) Subject: Re: Complexity of graph isomorphism Date: Mon, 13 Dec 1999 19:19:11 Newsgroups: sci.math.research In article <833b13$mfp$1@vixen.cso.uiuc.edu> c-blair@uiuc.edu (Charles Blair) writes: >From: c-blair@uiuc.edu (Charles Blair) >Subject: Complexity of graph isomorphism >Date: 13 Dec 1999 17:39:47 GMT > Is it still open whether this is an NP-complete problem? Yes, it is still open whether graph isomorphism is NP-complete. However, it is very very unlikely that it is that hard. E.g. it is known that the NP-completeness of graph isomorphism would imply that the polynomial hierarchy collapses to its second level (which is considered to be a very unlikely event). Graph isomorphism lies in co-NP and also in some probabilistically enhanced version of NP. Hence, it is "almost" contained in NP intersection co-NP. Etc. etc. etc. For more information, check out e.g. the book by Kvbler, Schvning, and Toran "The graph isomorphism problem: its structural complexity", Birkhduser 1993. - Gerhard ___________________________________________________________ Gerhard J. Woeginger (gwoegi@opt.math.tu-graz.ac.at)