To use all functions of this page, please activate cookies in your browser.
With an accout for my.chemeurope.com you can always see everything at a glance – and you can configure your own website and individual newsletter.
- My watch list
- My saved searches
- My saved topics
- My newsletter
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.
Additional recommended knowledge
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.
The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the clique problem. If subgraph isomorphism were polynomial, you could use it to solve the clique problem in polynomial time. Let n be the number of edges in G: you can then run the subgraph isomorphism n-2 times (with G1 being a clique of size 3 to n, and G2 being G) to find the largest clique in G.
Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem; if the graph isomorphism problem is NP-complete, the polynomial hierarchy collapses, so it is suspected not to be.
Also of main importance to graph grammars.
|This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Subgraph_isomorphism_problem". A list of authors is available in Wikipedia.|