Subgraph isomorphism problem
Encyclopedia : S : SU : SUB : Subgraph isomorphism problem
In complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. The formal description of the decision problem is as follows.
Subgraph-Isomorphism(G1, G2)
Input: Two graphs G1 and G2.
Question: Is G1 isomorphic to a subgraph of G2?
Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem.
Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem; if this problem is NP-complete, the polynomial hierarchy collapses, so it is suspected not to be.
Application areas
In the area of cheminformatics often the term substructure search is used. Typically a query structure is defined as SMARTS, a SMILES extension.See also
References
- Jeffrey D. Ullman: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
- A1.4: GT48, pg.202.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.