Article: 8616 of comp.theory Xref: moriarty.theory.cs.cmu.edu comp.theory:8616 Path: honeydew.srv.cs.cmu.edu!fs7.ECE.CMU.EDU!europa.eng.gtefsd.com!howland.reston.ans.net!usc!elroy.jpl.nasa.gov!ames!koriel!lll-winken.llnl.gov!diego.llnl.gov!cedeno From: wcedeno@llnl.gov Newsgroups: comp.theory Subject: Summary of responses for MCS problem. Date: 19 Nov 1993 14:58:02 GMT Organization: Lawrence Livermore National Laboratory, NCD Lines: 157 Distribution: inet Message-ID: <2cimtq$ae3@lll-winken.llnl.gov> NNTP-Posting-Host: diego.llnl.gov Keywords: MCS, isomorphism, graphs, NP-Complete Originator: cedeno@diego.llnl.gov Following is the summary on the responses I received on algorithms for finding the common subgraphs between two graphs. Thanks to all of you that assisted me with your info. From: Brendan McKay Hello Walter. My program "nauty" can compute automorphism groups and canonical labellings. The latter allows you to test isomorphism, but there is no built-in support for subgraph isomorphism. I distribute the program for free, but it is not public-domain. It is subject to my copyright and there are restrictions on usage and distribution. You can find it in directory pub/nauty19 on dcssoft.anu.edu.au (ftp login anonymous). The conditions of use and other information appear in the file read.me. There is also a manual there. ------------------ From: north@research.att.com Um, I know of some really fast code for graph automorphism. It's called "nauty" and was written by Brendan McKay. I think you can reach him at: bdm@anucsd.anu.edu.au. From: sandeep@cs.albany.edu ____________________ sandeep@cs.albany.edu The graph isomorphism problem has withstood all attempts at a solution till date. There are some conjectures that it is not even NP-Complete. For more references please see the Handbook of theoretical Computer Science Vol 1. ___________________ From: rbloem@prip.tuwien.ac.at (Roderick Bloem) You've struck quite a problem here. I have asked the same problem a couple of weeks ago, and it took me a lot of trouble to get some answers. The problem is that the problem is NP-complete. Now, you can do a couple of things: 1) Limit the type of graphs you consider. E.g. take only almost trees of bounded degree, or likewise. I believe the problem is NP-complete for planar graphs, so restriction to planarity won't bring you anything (I'm not sure though)... I can't restrict my graphs, so I do not know very much on this subject, but you could try: @ARTICLE{aku93, AUTHOR = {T. Akutsu}, TITLE = {A Polynomial Time Algorithm for Finding a Largest Common Subgraph of almost Trees of Bounded Degree}, JOURNAL = {IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences}, INSTITUTION= {IEICE}, YEAR = {1993}, VOLUME = {E76-A}, NUMBER = {9}, MONTH = {september}, KEYWORDS = {egbert, largest common subgraph, subgraph isomorphism, almost trees, np complete}, EMAIL = {}, } 2) Approximate the common subgraph. You can approximate the largest subgraph to a factor, meaning that you are not guaranteed to find the largest graph, but you'll find a neat approximation. Read the next three articles, they'll give you the background to write an algorithm: @InProceedings{kan92, Author = "V. Kann", Title = "On the approximability of the maximum common subgraph problem", BookTitle = "Proc. 9th Annual Symposium on Theoretical Aspects of Computer Science", Year = "1992", Publisher = "Springer", Pages = "377--388", Note = "Lecture Notes in Computer Science, number 577", Email = {}, Keywords = {egbert, maximum commom subgraph, subgraph isomorphism, approximability, np complete}, } @INPROCEEDINGS{bh90, AUTHOR = {R. Boppana and M.H. Halld\'orsson}, TITLE = {Approximating Maximum Independent Sets by Excluding Subgraphs}, BOOKTITLE = {Proc. SWAT 90}, PAGES = {13--25}, PUBLISHER = {Springer--Verlag}, YEAR = {1990}, NUMBER = {447}, SERIES = {Lecture notes in computer science}, KEYWORDS = {egbert, np complete, approximating, clique}, } @ARTICLE{bb75, AUTHOR = {H.G Barrow and R.M. Burstall}, TITLE = {Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques}, JOURNAL = {Information Processing Letters}, YEAR = {1975}, VOLUME = {E76-A}, NUMBER = {4}, PAGES = {83--84} KEYWORDS = {egbert, cliques, isomorphism, matching}, } 3) What the heck, I've got the computing time, let it be exponential. I've got the following references on that. I haven't checked them, though, so I don't know if they're any good. (sorry for the form...) ----- Hi, There's been lots of work in the area. What you're looking for is a Maximal Common Subgraph algorithm (or MCS for the jargon minded). A reference that I have to hand which will give you a starting point is; A.T. Brint and P. Willett, J.Chem Inf. Comput. Sci. 27, p 152 (1987). This describes various MCS algorithms and reviews their performance in chemical problems. There has been a lot of work done since then I'm sure, but I'm not up to date. Peter Willett's group at Sheffield Univ. in the UK is still working in the field, I believe. Looking at more recent papers of theirs might be a help. ----- The problem you describe is called substructure search. There has been a large body of work on this subject as it is an integral part of many areas of computational chemistry. For a practical approach to the problem look up the paper by dengler and ugi, computers in chemistry, V15, N2, pp 103-107, 1991. It describes a program called cabass for which fortan source is available. You will need to write to: EFONTAIN@nucleus.org.chemie.tu-muenchen.de in prof. ugi's group to find the address of Alf Dengler (Alf has the fortran source). If you have any other offers of source code I'd really like to hear about them. Searching for references on substructure search will provide you with a multitude of other papers, but few are describe the implimentation as well as the ugi paper. ---- ________________ Other things Three Dimensional Chemical Structure Handling, Peter Willett, 1991. RSP. Crandell & Smith, 1983:Computer assisted examination of compounds for common 3D substructures. J. of Chem Inf and Comp Sciences, 23, 186-197. McGregor, J. J., 1982: Backtrack search algorithms and the MCS problem. Software - Practice and Experience, 12, 23-34.