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 also name subgraph matching is used for the same problem. This name puts emphasis on finding such a subgraph and is not a bare decision problem.
Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem.Template:Math-stub