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.